<!DOCTYPE html>
<html dir="ltr" class="client-js" lang="en"><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Burrows–Wheeler transform - Wikipedia, the free encyclopedia</title>
<meta charset="UTF-8">
<meta name="generator" content="MediaWiki 1.21wmf7">
<link rel="alternate" type="application/x-wiki" title="Edit this page" href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit">
<link rel="edit" title="Edit this page" href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit">
<link rel="apple-touch-icon" href="http://en.wikipedia.org/apple-touch-icon.png">
<link rel="shortcut icon" href="http://en.wikipedia.org/favicon.ico">
<link rel="search" type="application/opensearchdescription+xml" href="http://en.wikipedia.org/w/opensearch_desc.php" title="Wikipedia (en)">
<link rel="EditURI" type="application/rsd+xml" href="http://en.wikipedia.org/w/api.php?action=rsd">
<link rel="copyright" href="http://creativecommons.org/licenses/by-sa/3.0/">
<link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="http://en.wikipedia.org/w/index.php?title=Special:RecentChanges&amp;feed=atom">
<link rel="stylesheet" href="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_002.css">
<style>#wpTextbox1{margin:0;display:block}.editOptions{background-color:#F0F0F0;border:1px solid silver;border-top:none;padding:1em 1em 1.5em 1em;margin-bottom:2em}.collapsible-list{display:inline;cursor:pointer;min-width:400px}.collapsible-list > span{float:left;background:url();background:url(//bits.wikimedia.org/static-1.21wmf7/extensions/Vector/modules/./images/open.png?2013-01-02T19:40:00Z)!ie;background-repeat:no-repeat;background-position:50% 50%;display:block;height:16px;width:16px}.collapsible-list > span.collapsed{background:url();background:url(//bits.wikimedia.org/static-1.21wmf7/extensions/Vector/modules/./images/closed-ltr.png?2013-01-02T19:40:00Z)!ie;background-repeat:no-repeat;background-position:50% 50%}.hiddencats > ul,.templatesUsed > ul{margin:1em 2.5em}.editCheckboxes{margin-bottom:1em}.editCheckboxes input[type='checkbox']:first-child{margin-left:0}.cancelLink{margin:0 0.5em}.cancelLinkPipeSpace{display:inline-block;width:0.5em;height:0.5em}#editpage-copywarn{font-size:0.9em}input#wpSummary{display:block;margin-top:0;margin-bottom:0.5em}.editButtons > input[type='submit']:first-child{margin-left:.1em}
/* cache key: enwiki:resourceloader:filter:minify-css:7:7139ea9ce0afdd8f0db5d42a14fe7d2a */.mw-mah-wrapper a{cursor:pointer}.mw-mah-wrapper .mah-helpful-state{background:transparent url() no-repeat left center;background:transparent url(//bits.wikimedia.org/static-1.21wmf7/extensions/MarkAsHelpful/modules/ext.markAsHelpful/images/mah-helpful-dull.png?2013-01-02T19:38:20Z) no-repeat left center!ie;padding-left:18px}.mw-mah-wrapper .mah-helpful-state:hover{background:transparent url() no-repeat left center;background:transparent url(//bits.wikimedia.org/static-1.21wmf7/extensions/MarkAsHelpful/modules/ext.markAsHelpful/images/mah-helpful-hover.png?2013-01-02T19:38:20Z) no-repeat left center!ie}.mw-mah-wrapper .mah-helpful-marked-state{background:transparent url() no-repeat left center;background:transparent url(//bits.wikimedia.org/static-1.21wmf7/extensions/MarkAsHelpful/modules/ext.markAsHelpful/images/mah-helpful-marked.png?2013-01-02T19:38:20Z) no-repeat left center!ie;padding-left:18px}
/* cache key: enwiki:resourceloader:filter:minify-css:7:e540b97bc33a66fbbc8e4dfab0a607e8 */.postedit-container{margin:0 auto;position:fixed;top:2%;left:50%;z-index:1000}.postedit{position:relative;top:0;left:-50%;padding:.6em 3.6em .6em 1.1em;font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;font-size:0.8em;line-height:1.5625em;color:#626465;background:#eee url() repeat-x;background:#eee url(//bits.wikimedia.org/static-1.21wmf7/extensions/PostEdit/resources/images/gray-bg.png?2013-01-02T19:38:20Z) repeat-x!ie;border:1px solid #dcd9d9;-webkit-text-shadow:0 0.0625em 0 rgba(255,255,255,0.5);-moz-text-shadow:0 0.0625em 0 rgba(255,255,255,0.5);text-shadow:0 0.0625em 0 rgba(255,255,255,0.5);-webkit-border-radius:5px;-moz-border-radius:5px;border-radius:5px;-webkit-box-shadow:0 2px 5px 0 #ccc;-moz-box-shadow:0 2px 5px 0 #ccc;box-shadow:0 2px 5px 0 #ccc;-webkit-transition:all 0.25s ease-in-out;-moz-transition:all 0.25s ease-in-out;-ms-transition:all 0.25s ease-in-out;-o-transition:all 0.25s ease-in-out;transition:all 0.25s ease-in-out}.postedit-faded{opacity:0}.postedit-icon{padding-left:41px;  line-height:25px;background-repeat:no-repeat;background-position:8px 50%}.postedit-icon-checkmark{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/PostEdit/resources/images/green-checkmark.png?2013-01-02T19:38:20Z)!ie;background-position:left}.postedit-close{position:absolute;top:.6em;right:.8em;font-size:1.25em;font-weight:bold;line-height:1.1em;color:black;text-shadow:0 0.0625em 0 white;text-decoration:none;opacity:0.2;filter:alpha(opacity=20)}.postedit-close:hover{color:black;text-decoration:none;cursor:pointer;opacity:0.4;filter:alpha(opacity=40)}
/* cache key: enwiki:resourceloader:filter:minify-css:7:abe9843ec2594d43c9de695b3eb4bede */.referencetooltip{position:absolute;list-style:none;list-style-image:none;opacity:0;font-size:10px;margin:0;z-index:5;padding:0}.referencetooltip li{border:#080086 2px solid;max-width:260px;padding:10px 8px 13px 8px;margin:0px;background-color:#F7F7F7;box-shadow:2px 4px 2px rgba(0,0,0,0.3);-moz-box-shadow:2px 4px 2px rgba(0,0,0,0.3);-webkit-box-shadow:2px 4px 2px rgba(0,0,0,0.3)}.referencetooltip li+li{margin-left:7px;margin-top:-2px;border:0;padding:0;height:3px;width:0px;background-color:transparent;box-shadow:none;-moz-box-shadow:none;-webkit-box-shadow:none;border-top:12px #080086 solid;border-right:7px transparent solid;border-left:7px transparent solid}.referencetooltip>li+li::after{content:'';border-top:8px #F7F7F7 solid;border-right:5px transparent solid;border-left:5px transparent solid;margin-top:-12px;margin-left:-5px;z-index:1;height:0px;width:0px;display:block}.client-js .referencetooltip li ul li{border:none;box-shadow:none;-moz-box-shadow:none;-webkit-box-shadow:none;height:auto;width:auto;margin:auto;padding:0;position:static}.RTflipped{padding-top:13px}.referencetooltip.RTflipped li+li{position:absolute;top:2px;border-top:0;border-bottom:12px #080086 solid}.referencetooltip.RTflipped li+li::after{border-top:0;border-bottom:8px #F7F7F7 solid;position:absolute;margin-top:7px}.RTsettings{float:right;height:16px;width:16px;cursor:pointer;background-image:url(//upload.wikimedia.org/wikipedia/commons/e/ed/Cog.png);margin-top:-9px;margin-right:-7px;-webkit-transition:opacity 0.15s;-moz-transition:opacity 0.15s;-o-transition:opacity 0.15s;-ms-transition:opacity 0.15s;transition:opacity 0.15s;opacity:0.6;filter:alpha(opacity=60)}.RTsettings:hover{opacity:1;filter:alpha(opacity=100)}
/* cache key: enwiki:resourceloader:filter:minify-css:7:f043a32bb7f4917227bd98422c2a56ec */div#editpage-specialchars{display:block;margin-top:.5em;border:1px solid #c0c0c0;padding:.3em}
/* cache key: enwiki:resourceloader:filter:minify-css:7:29386c84f9c8f19dfb410df7e5be154b */.mw-collapsible-toggle{float:right} li .mw-collapsible-toggle{float:none} .mw-collapsible-toggle-li{list-style:none}
/* cache key: enwiki:resourceloader:filter:minify-css:7:4250852ed2349a0d4d0fc6509a3e7d4c */.suggestions{overflow:hidden;position:absolute;top:0;left:0;width:0;border:none;z-index:1099;padding:0;margin:-1px -1px 0 0} html > body .suggestions{margin:-1px 0 0 0}.suggestions-special{position:relative;background-color:white;cursor:pointer;border:solid 1px #aaaaaa;padding:0;margin:0;margin-top:-2px;display:none;padding:0.25em 0.25em;line-height:1.25em}.suggestions-results{background-color:white;cursor:pointer;border:solid 1px #aaaaaa;padding:0;margin:0}.suggestions-result{color:black;margin:0;line-height:1.5em;padding:0.01em 0.25em;text-align:left}.suggestions-result-current{background-color:#4C59A6;color:white}.suggestions-special .special-label{color:gray;text-align:left}.suggestions-special .special-query{color:black;font-style:italic;text-align:left}.suggestions-special .special-hover{background-color:silver}.suggestions-result-current .special-label,.suggestions-result-current .special-query{color:white}.autoellipsis-matched,.highlight{font-weight:bold}
/* cache key: enwiki:resourceloader:filter:minify-css:7:9780324491b653a3780e2d029bdc140c */#container{position:relative;min-height:100%}#container,video{width:100%;height:100%}#playerContainer{overflow:hidden;position:relative;height:100%;background:#000}#videoHolder{position:relative;overflow:hidden}.fullscreen #playerContainer{position:absolute !important;width:100% !important;height:100%! important;z-index:9999;min-height:100%;top:0;left:0;margin:0}.mwEmbedPlayer{width:100%;height:100%;overflow:hidden;position:absolute;top:0;left:0}.modal_editor{ left:10px;top:10px;right:10px;bottom:10px;position:fixed;z-index:100}.displayHTML a:visited{color:white}.loadingSpinner{width:32px;height:32px;display:block;padding:0px;background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/MwEmbedSupport/MwEmbedModules/MwEmbedSupport/skins/common/images/loading_ani.gif?2013-01-02T19:38:20Z)}.mw-imported-resource{border:thin solid black}.kaltura-icon{background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/MwEmbedSupport/MwEmbedModules/MwEmbedSupport/skins/common/images/kaltura_logo_sm_transparent.png?2013-01-02T19:38:20Z) !important;background-repeat:no-repeat;display:block;height:12px;width:12px;margin-top:2px !important;margin-left:3px !important}.mw-fullscreen-overlay{background:rgb(0,0,0) none repeat scroll 0% 0%;position:fixed;top:0pt;left:0pt;width:100%;height:100%;-moz-background-clip:border;-moz-background-origin:padding;-moz-background-inline-policy:continuous} .play-btn-large{width:70px;height:53px;background :url(//bits.wikimedia.org/static-1.21wmf7/extensions/MwEmbedSupport/MwEmbedModules/MwEmbedSupport/skins/common/images/player_big_play_button.png?2013-01-02T19:38:20Z);position :absolute;cursor :pointer;border :none !important;z-index :1}.play-btn-large:hover{background :url(//bits.wikimedia.org/static-1.21wmf7/extensions/MwEmbedSupport/MwEmbedModules/MwEmbedSupport/skins/common/images/player_big_play_button_hover.png?2013-01-02T19:38:20Z)}.carouselContainer{position :absolute;width :100%;z-index :2}.carouselVideoTitle{position :absolute;top :0px;left :0px;width :100%;background :rgba(0,0,0,0.8);color :white;font-size :small;font-weight :bold;z-index :2}.carouselVideoTitleText{display :block;padding :10px 10px 10px 20px}.carouselTitleDuration{position :absolute;top :0px;right :0px;padding :2px;background-color :#5A5A5A;color :#D9D9D9;font-size :smaller;z-index :2}.carouselImgTitle{position :absolute;width :100%;text-align :center;color :white;font-size :small;background :rgba(0,0,0,0.4)}.carouselImgDuration{position :absolute;top :2px;left :2px;background :rgba( 0,0,0,0.7 );color :white;padding :1px 6px;font-size :small}.carouselPrevButton,.carouselNextButton{display :block;position :absolute;bottom:23px}.carouselPrevButton{left :5px}.carouselNextButton{right:6px}.alert-container{-webkit-border-radius:3px;-moz-border-radius:3px;border-radius:3px;background-image:linear-gradient(bottom,rgb(215,215,215) 4%,rgb(230,230,230) 55%,rgb(255,255,255) 100%);background-image:-o-linear-gradient(bottom,rgb(215,215,215) 4%,rgb(230,230,230) 55%,rgb(255,255,255) 100%);background-image:-moz-linear-gradient(bottom,rgb(215,215,215) 4%,rgb(230,230,230) 55%,rgb(255,255,255) 100%);background-image:-webkit-linear-gradient(bottom,rgb(215,215,215) 4%,rgb(230,230,230) 55%,rgb(255,255,255) 100%);background-image:-ms-linear-gradient(bottom,rgb(215,215,215) 4%,rgb(230,230,230) 55%,rgb(255,255,255) 100%);background-image:-webkit-gradient(linear,left bottom,left top,color-stop(0.04,rgb(215,215,215)),color-stop(0.55,rgb(230,230,230)),color-stop(1,rgb(255,255,255)));margin:auto;position:absolute;top:0;left:0;right:0;bottom:0;max-width:80%;max-height:30%}.alert-title{background-color :#E6E6E6;padding :5px;border-bottom :1px solid #D1D1D1;font-weight :normal !important;font-size:14px !important;-webkit-border-top-left-radius:3px;-moz-border-radius-topleft:3px;border-top-left-radius:3px;-webkit-border-top-right-radius:3px;-moz-border-radius-topright:3px;border-top-right-radius:3px }.alert-message{padding :5px;font-weight :normal !important;text-align:center;font-size:14px !important}.alert-buttons-container{text-align:center;padding-bottom:5px}.alert-button{background-color:#474747;color:white;-webkit-border-radius:.5em;-moz-border-radius:.5em;border-radius:.5em;padding:2px 10px;background-image:linear-gradient(bottom,rgb(25,25,25) 4%,rgb(47,47,47) 55%,rgb(71,71,71) 68%);background-image:-o-linear-gradient(bottom,rgb(25,25,25) 4%,rgb(47,47,47) 55%,rgb(71,71,71) 68%);background-image:-moz-linear-gradient(bottom,rgb(25,25,25) 4%,rgb(47,47,47) 55%,rgb(71,71,71) 68%);background-image:-webkit-linear-gradient(bottom,rgb(25,25,25) 4%,rgb(47,47,47) 55%,rgb(71,71,71) 68%);background-image:-ms-linear-gradient(bottom,rgb(25,25,25) 4%,rgb(47,47,47) 55%,rgb(71,71,71) 68%);background-image:-webkit-gradient( linear,left bottom,left top,color-stop(0.04,rgb(25,25,25)),color-stop(0.55,rgb(47,47,47)),color-stop(0.68,rgb(71,71,71)) )}.alert-text{color :black !important}
/* cache key: enwiki:resourceloader:filter:minify-css:7:e8397ce2a428e11f37eed88f14fe9ba3 */#mw-panel.collapsible-nav .portal{background:url() left top no-repeat;background:url(//bits.wikimedia.org/static-1.21wmf7/extensions/Vector/modules/images/portal-break.png?2013-01-02T19:40:00Z) left top no-repeat!ie;padding:0.25em 0 !important;margin:-11px 9px 10px 11px}#mw-panel.collapsible-nav .portal h3,#mw-panel.collapsible-nav .portal h5{color:#4D4D4D;font-weight:normal;background:url() left center no-repeat;background:url(//bits.wikimedia.org/static-1.21wmf7/extensions/Vector/modules/images/open.png?2013-01-02T19:40:00Z) left center no-repeat!ie;padding:4px 0 3px 1.5em;margin-bottom:0}#mw-panel.collapsible-nav .portal h3:hover,#mw-panel.collapsible-nav .portal h5:hover{cursor:pointer;text-decoration:none}#mw-panel.collapsible-nav .portal h3 a,#mw-panel.collapsible-nav .portal h5 a{color:#4D4D4D;text-decoration:none}#mw-panel.collapsible-nav .portal .body{background:none !important;padding-top:0;display:none}#mw-panel.collapsible-nav .portal .body ul li{padding:0.25em 0} #mw-panel.collapsible-nav .portal.first h3,#mw-panel.collapsible-nav .portal.first h5{display:none}#mw-panel.collapsible-nav .portal.first{background-image:none;margin-top:0} #mw-panel.collapsible-nav .portal.persistent .body{display:block}#mw-panel.collapsible-nav .portal.persistent h3,#mw-panel.collapsible-nav .portal.persistent h5{background:none !important;padding-left:0.7em;cursor:default}#mw-panel.collapsible-nav .portal.persistent .body{margin-left:0.5em} #mw-panel.collapsible-nav .portal.collapsed h3,#mw-panel.collapsible-nav .portal.collapsed h5{color:#0645AD;background:url() left center no-repeat;background:url(//bits.wikimedia.org/static-1.21wmf7/extensions/Vector/modules/images/closed-ltr.png?2013-01-02T19:40:00Z) left center no-repeat!ie;margin-bottom:0}#mw-panel.collapsible-nav .portal.collapsed h3 a,#mw-panel.collapsible-nav .portal.collapsed h5 a{color:#0645AD}#mw-panel.collapsible-nav .portal.collapsed h3:hover,#mw-panel.collapsible-nav .portal.collapsed h5:hover{text-decoration:underline}
/* cache key: enwiki:resourceloader:filter:minify-css:7:43abf1bb9891ff21eb4862e713dd7e21 */.ui-helper-hidden{display:none}.ui-helper-hidden-accessible{position:absolute;left:-99999999px}.ui-helper-reset{margin:0;padding:0;border:0;outline:0;line-height:1.3;text-decoration:none;font-size:100%;list-style:none}.ui-helper-clearfix:after{content:".";display:block;height:0;clear:both;visibility:hidden}.ui-helper-clearfix{display:inline-block} * html .ui-helper-clearfix{height:1%}.ui-helper-clearfix{display:block} .ui-helper-zfix{width:100%;height:100%;top:0;left:0;position:absolute;opacity:0;filter:Alpha(Opacity=0)} .ui-state-disabled{cursor:default !important}  .ui-icon{display:block;text-indent:-99999px;overflow:hidden;background-repeat:no-repeat}  .ui-widget-overlay{position:absolute;top:0;left:0;width:100%;height:100%}  .ui-widget{font-family:sans-serif;font-size:0.8em}.ui-widget .ui-widget{font-size:1em}.ui-widget input,.ui-widget select,.ui-widget textarea,.ui-widget button{font-family:sans-serif;font-size:1em}.ui-widget-content{border:1px solid #cccccc;background:#f2f5f7 url() 50% top repeat-x;background:#f2f5f7 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_highlight-hard_100_f2f5f7_1x100.png?2013-01-02T16:11:40Z) 50% top repeat-x!ie;color:#362b36}.ui-widget-content a{color:#362b36}.ui-widget-header{border-bottom:1px solid #bbbbbb;line-height:1em;background:#ffffff url() 50% 50% repeat-x;background:#ffffff url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_highlight-soft_100_ffffff_1x100.png?2013-01-02T16:11:40Z) 50% 50% repeat-x!ie;color:#222222;font-weight:bold}.ui-widget-header a{color:#222222} .ui-state-default,.ui-widget-content .ui-state-default,.ui-widget-header .ui-state-default{border:1px solid #aed0ea;background:#d7ebf9 url() 50% 50% repeat-x;background:#d7ebf9 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_highlight-hard_80_d7ebf9_1x100.png?2013-01-02T16:11:40Z) 50% 50% repeat-x!ie;font-weight:normal;color:#2779aa}.ui-state-default a,.ui-state-default a:link,.ui-state-default a:visited{color:#2779aa;text-decoration:none}.ui-state-hover,.ui-widget-content .ui-state-hover,.ui-widget-header .ui-state-hover,.ui-state-focus,.ui-widget-content .ui-state-focus,.ui-widget-header .ui-state-focus{border:1px solid #74b2e2;background:#e4f1fb url() 50% 50% repeat-x;background:#e4f1fb url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_highlight-soft_100_e4f1fb_1x100.png?2013-01-02T16:11:40Z) 50% 50% repeat-x!ie;font-weight:normal;color:#0070a3}.ui-state-hover a,.ui-state-hover a:hover{color:#0070a3;text-decoration:none}.ui-state-active,.ui-widget-content .ui-state-active,.ui-widget-header .ui-state-active{border:1px solid #cccccc;background:#f0f0f0 url() 50% 50% repeat-x;url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_inset-hard_100_f0f0f0_1x100.png?2013-01-02T16:11:40Z) 50% 50% repeat-x!ie;font-weight:normal;color:#000000}.ui-state-active a,.ui-state-active a:link,.ui-state-active a:visited{color:#000000;text-decoration:none}.ui-widget :active{outline:none} .ui-state-highlight,.ui-widget-content .ui-state-highlight,.ui-widget-header .ui-state-highlight{border:1px solid #f9dd34;background:#ffef8f url() 50% top repeat-x;url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_highlight-soft_25_ffef8f_1x100.png?2013-01-02T16:11:40Z) 50% top repeat-x!ie;color:#363636}.ui-state-highlight a,.ui-widget-content .ui-state-highlight a,.ui-widget-header .ui-state-highlight a{color:#363636}.ui-state-error,.ui-widget-content .ui-state-error,.ui-widget-header .ui-state-error{border:1px solid #cd0a0a;background:#cd0a0a url() 50% 50% repeat-x;url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_flat_15_cd0a0a_40x100.png?2013-01-02T16:11:40Z) 50% 50% repeat-x!ie;color:#ffffff}.ui-state-error a,.ui-widget-content .ui-state-error a,.ui-widget-header .ui-state-error a{color:#ffffff}.ui-state-error-text,.ui-widget-content .ui-state-error-text,.ui-widget-header .ui-state-error-text{color:#ffffff}.ui-priority-primary,.ui-widget-content .ui-priority-primary,.ui-widget-header .ui-priority-primary{font-weight:bold}.ui-priority-secondary,.ui-widget-content .ui-priority-secondary,.ui-widget-header .ui-priority-secondary{opacity:.7;filter:Alpha(Opacity=70);font-weight:normal}.ui-state-disabled,.ui-widget-content .ui-state-disabled,.ui-widget-header .ui-state-disabled{opacity:.35;filter:Alpha(Opacity=35);background-image:none}  .ui-icon{width:16px;height:16px}.ui-icon,.ui-widget-content .ui-icon,.ui-widget-header .ui-icon{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_72a7cf_256x240.png?2013-01-02T16:11:40Z)!ie}.ui-state-default .ui-icon{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_3d80b3_256x240.png?2013-01-02T16:11:40Z)!ie}.ui-state-hover .ui-icon,.ui-state-focus .ui-icon{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_2694e8_256x240.png?2013-01-02T16:11:40Z)!ie}.ui-state-active .ui-icon{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_666666_256x240.png?2013-01-02T16:11:40Z)!ie}.ui-state-highlight .ui-icon{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_2e83ff_256x240.png?2013-01-02T16:11:40Z)!ie}.ui-state-error .ui-icon,.ui-state-error-text .ui-icon{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_ffffff_256x240.png?2013-01-02T16:11:40Z)!ie} .ui-icon-carat-1-n{background-position:0 0}.ui-icon-carat-1-ne{background-position:-16px 0}.ui-icon-carat-1-e{background-position:-32px 0}.ui-icon-carat-1-se{background-position:-48px 0}.ui-icon-carat-1-s{background-position:-64px 0}.ui-icon-carat-1-sw{background-position:-80px 0}.ui-icon-carat-1-w{background-position:-96px 0}.ui-icon-carat-1-nw{background-position:-112px 0}.ui-icon-carat-2-n-s{background-position:-128px 0}.ui-icon-carat-2-e-w{background-position:-144px 0}.ui-icon-triangle-1-n{background-position:0 -16px}.ui-icon-triangle-1-ne{background-position:-16px -16px}.ui-icon-triangle-1-e{background-position:-32px -16px}.ui-icon-triangle-1-se{background-position:-48px -16px}.ui-icon-triangle-1-s{background-position:-64px -16px}.ui-icon-triangle-1-sw{background-position:-80px -16px}.ui-icon-triangle-1-w{background-position:-96px -16px}.ui-icon-triangle-1-nw{background-position:-112px -16px}.ui-icon-triangle-2-n-s{background-position:-128px -16px}.ui-icon-triangle-2-e-w{background-position:-144px -16px}.ui-icon-arrow-1-n{background-position:0 -32px}.ui-icon-arrow-1-ne{background-position:-16px -32px}.ui-icon-arrow-1-e{background-position:-32px -32px}.ui-icon-arrow-1-se{background-position:-48px -32px}.ui-icon-arrow-1-s{background-position:-64px -32px}.ui-icon-arrow-1-sw{background-position:-80px -32px}.ui-icon-arrow-1-w{background-position:-96px -32px}.ui-icon-arrow-1-nw{background-position:-112px -32px}.ui-icon-arrow-2-n-s{background-position:-128px -32px}.ui-icon-arrow-2-ne-sw{background-position:-144px -32px}.ui-icon-arrow-2-e-w{background-position:-160px -32px}.ui-icon-arrow-2-se-nw{background-position:-176px -32px}.ui-icon-arrowstop-1-n{background-position:-192px -32px}.ui-icon-arrowstop-1-e{background-position:-208px -32px}.ui-icon-arrowstop-1-s{background-position:-224px -32px}.ui-icon-arrowstop-1-w{background-position:-240px -32px}.ui-icon-arrowthick-1-n{background-position:0 -48px}.ui-icon-arrowthick-1-ne{background-position:-16px -48px}.ui-icon-arrowthick-1-e{background-position:-32px -48px}.ui-icon-arrowthick-1-se{background-position:-48px -48px}.ui-icon-arrowthick-1-s{background-position:-64px -48px}.ui-icon-arrowthick-1-sw{background-position:-80px -48px}.ui-icon-arrowthick-1-w{background-position:-96px -48px}.ui-icon-arrowthick-1-nw{background-position:-112px -48px}.ui-icon-arrowthick-2-n-s{background-position:-128px -48px}.ui-icon-arrowthick-2-ne-sw{background-position:-144px -48px}.ui-icon-arrowthick-2-e-w{background-position:-160px -48px}.ui-icon-arrowthick-2-se-nw{background-position:-176px -48px}.ui-icon-arrowthickstop-1-n{background-position:-192px -48px}.ui-icon-arrowthickstop-1-e{background-position:-208px -48px}.ui-icon-arrowthickstop-1-s{background-position:-224px -48px}.ui-icon-arrowthickstop-1-w{background-position:-240px -48px}.ui-icon-arrowreturnthick-1-w{background-position:0 -64px}.ui-icon-arrowreturnthick-1-n{background-position:-16px -64px}.ui-icon-arrowreturnthick-1-e{background-position:-32px -64px}.ui-icon-arrowreturnthick-1-s{background-position:-48px -64px}.ui-icon-arrowreturn-1-w{background-position:-64px -64px}.ui-icon-arrowreturn-1-n{background-position:-80px -64px}.ui-icon-arrowreturn-1-e{background-position:-96px -64px}.ui-icon-arrowreturn-1-s{background-position:-112px -64px}.ui-icon-arrowrefresh-1-w{background-position:-128px -64px}.ui-icon-arrowrefresh-1-n{background-position:-144px -64px}.ui-icon-arrowrefresh-1-e{background-position:-160px -64px}.ui-icon-arrowrefresh-1-s{background-position:-176px -64px}.ui-icon-arrow-4{background-position:0 -80px}.ui-icon-arrow-4-diag{background-position:-16px -80px}.ui-icon-extlink{background-position:-32px -80px}.ui-icon-newwin{background-position:-48px -80px}.ui-icon-refresh{background-position:-64px -80px}.ui-icon-shuffle{background-position:-80px -80px}.ui-icon-transfer-e-w{background-position:-96px -80px}.ui-icon-transferthick-e-w{background-position:-112px -80px}.ui-icon-folder-collapsed{background-position:0 -96px}.ui-icon-folder-open{background-position:-16px -96px}.ui-icon-document{background-position:-32px -96px}.ui-icon-document-b{background-position:-48px -96px}.ui-icon-note{background-position:-64px -96px}.ui-icon-mail-closed{background-position:-80px -96px}.ui-icon-mail-open{background-position:-96px -96px}.ui-icon-suitcase{background-position:-112px -96px}.ui-icon-comment{background-position:-128px -96px}.ui-icon-person{background-position:-144px -96px}.ui-icon-print{background-position:-160px -96px}.ui-icon-trash{background-position:-176px -96px}.ui-icon-locked{background-position:-192px -96px}.ui-icon-unlocked{background-position:-208px -96px}.ui-icon-bookmark{background-position:-224px -96px}.ui-icon-tag{background-position:-240px -96px}.ui-icon-home{background-position:0 -112px}.ui-icon-flag{background-position:-16px -112px}.ui-icon-calendar{background-position:-32px -112px}.ui-icon-cart{background-position:-48px -112px}.ui-icon-pencil{background-position:-64px -112px}.ui-icon-clock{background-position:-80px -112px}.ui-icon-disk{background-position:-96px -112px}.ui-icon-calculator{background-position:-112px -112px}.ui-icon-zoomin{background-position:-128px -112px}.ui-icon-zoomout{background-position:-144px -112px}.ui-icon-search{background-position:-160px -112px}.ui-icon-wrench{background-position:-176px -112px}.ui-icon-gear{background-position:-192px -112px}.ui-icon-heart{background-position:-208px -112px}.ui-icon-star{background-position:-224px -112px}.ui-icon-link{background-position:-240px -112px}.ui-icon-cancel{background-position:0 -128px}.ui-icon-plus{background-position:-16px -128px}.ui-icon-plusthick{background-position:-32px -128px}.ui-icon-minus{background-position:-48px -128px}.ui-icon-minusthick{background-position:-64px -128px}.ui-icon-close{background-position:-80px -128px}.ui-icon-closethick{background-position:-96px -128px}.ui-icon-key{background-position:-112px -128px}.ui-icon-lightbulb{background-position:-128px -128px}.ui-icon-scissors{background-position:-144px -128px}.ui-icon-clipboard{background-position:-160px -128px}.ui-icon-copy{background-position:-176px -128px}.ui-icon-contact{background-position:-192px -128px}.ui-icon-image{background-position:-208px -128px}.ui-icon-video{background-position:-224px -128px}.ui-icon-script{background-position:-240px -128px}.ui-icon-alert{background-position:0 -144px}.ui-icon-info{background-position:-16px -144px}.ui-icon-notice{background-position:-32px -144px}.ui-icon-help{background-position:-48px -144px}.ui-icon-check{background-position:-64px -144px}.ui-icon-bullet{background-position:-80px -144px}.ui-icon-radio-off{background-position:-96px -144px}.ui-icon-radio-on{background-position:-112px -144px}.ui-icon-pin-w{background-position:-128px -144px}.ui-icon-pin-s{background-position:-144px -144px}.ui-icon-play{background-position:0 -160px}.ui-icon-pause{background-position:-16px -160px}.ui-icon-seek-next{background-position:-32px -160px}.ui-icon-seek-prev{background-position:-48px -160px}.ui-icon-seek-end{background-position:-64px -160px}.ui-icon-seek-start{background-position:-80px -160px} .ui-icon-seek-first{background-position:-80px -160px}.ui-icon-stop{background-position:-96px -160px}.ui-icon-eject{background-position:-112px -160px}.ui-icon-volume-off{background-position:-128px -160px}.ui-icon-volume-on{background-position:-144px -160px}.ui-icon-power{background-position:0 -176px}.ui-icon-signal-diag{background-position:-16px -176px}.ui-icon-signal{background-position:-32px -176px}.ui-icon-battery-0{background-position:-48px -176px}.ui-icon-battery-1{background-position:-64px -176px}.ui-icon-battery-2{background-position:-80px -176px}.ui-icon-battery-3{background-position:-96px -176px}.ui-icon-circle-plus{background-position:0 -192px}.ui-icon-circle-minus{background-position:-16px -192px}.ui-icon-circle-close{background-position:-32px -192px}.ui-icon-circle-triangle-e{background-position:-48px -192px}.ui-icon-circle-triangle-s{background-position:-64px -192px}.ui-icon-circle-triangle-w{background-position:-80px -192px}.ui-icon-circle-triangle-n{background-position:-96px -192px}.ui-icon-circle-arrow-e{background-position:-112px -192px}.ui-icon-circle-arrow-s{background-position:-128px -192px}.ui-icon-circle-arrow-w{background-position:-144px -192px}.ui-icon-circle-arrow-n{background-position:-160px -192px}.ui-icon-circle-zoomin{background-position:-176px -192px}.ui-icon-circle-zoomout{background-position:-192px -192px}.ui-icon-circle-check{background-position:-208px -192px}.ui-icon-circlesmall-plus{background-position:0 -208px}.ui-icon-circlesmall-minus{background-position:-16px -208px}.ui-icon-circlesmall-close{background-position:-32px -208px}.ui-icon-squaresmall-plus{background-position:-48px -208px}.ui-icon-squaresmall-minus{background-position:-64px -208px}.ui-icon-squaresmall-close{background-position:-80px -208px}.ui-icon-grip-dotted-vertical{background-position:0 -224px}.ui-icon-grip-dotted-horizontal{background-position:-16px -224px}.ui-icon-grip-solid-vertical{background-position:-32px -224px}.ui-icon-grip-solid-horizontal{background-position:-48px -224px}.ui-icon-gripsmall-diagonal-se{background-position:-64px -224px}.ui-icon-grip-diagonal-se{background-position:-80px -224px}  .ui-corner-tl{-moz-border-radius-topleft:0;-webkit-border-top-left-radius:0}.ui-corner-tr{-moz-border-radius-topright:0;-webkit-border-top-right-radius:0}.ui-corner-bl{-moz-border-radius-bottomleft:0;-webkit-border-bottom-left-radius:0}.ui-corner-br{-moz-border-radius-bottomright:0;-webkit-border-bottom-right-radius:0}.ui-corner-top{-moz-border-radius-topleft:0;-webkit-border-top-left-radius:0;-moz-border-radius-topright:0;-webkit-border-top-right-radius:0}.ui-corner-bottom{-moz-border-radius-bottomleft:0;-webkit-border-bottom-left-radius:0;-moz-border-radius-bottomright:0;-webkit-border-bottom-right-radius:0}.ui-corner-right{-moz-border-radius-topright:0;-webkit-border-top-right-radius:0;-moz-border-radius-bottomright:0;-webkit-border-bottom-right-radius:0}.ui-corner-left{-moz-border-radius-topleft:0;-webkit-border-top-left-radius:0;-moz-border-radius-bottomleft:0;-webkit-border-bottom-left-radius:0}.ui-corner-all{-moz-border-radius:0;-webkit-border-radius:0} .ui-widget-overlay{background:#000000;opacity:.75;filter:Alpha(Opacity=75)}.ui-widget-shadow{margin:-7px 0 0 -7px;padding:7px;background:#000000 url() 50% 50% repeat-x;background:#000000 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-bg_flat_70_000000_40x100.png?2013-01-02T16:11:40Z) 50% 50% repeat-x!ie;opacity:.20;filter:Alpha(Opacity=20);-moz-border-radius:8px;-webkit-border-radius:8px;border-radius:8px}
/* cache key: enwiki:resourceloader:filter:minify-css:7:d2fef9b89ab86a82417beda40afd080f */.ui-resizable{position:relative}.ui-resizable-handle{position:absolute;font-size:0.1px;z-index:99999;display:block}.ui-resizable-disabled .ui-resizable-handle,.ui-resizable-autohide .ui-resizable-handle{display:none}.ui-resizable-n{cursor:n-resize;height:7px;width:100%;top:-5px;left:0}.ui-resizable-s{cursor:s-resize;height:7px;width:100%;bottom:-5px;left:0} .ui-resizable-e{cursor:e-resize;width:7px;right:-5px;top:0;height:100%} .ui-resizable-w{cursor:w-resize;width:7px;left:-5px;top:0;height:100%} .ui-resizable-se{cursor:se-resize;width:12px;height:12px;right:1px;bottom:1px} .ui-resizable-sw{cursor:sw-resize;width:9px;height:9px;left:-5px;bottom:-5px} .ui-resizable-nw{cursor:nw-resize;width:9px;height:9px;left:-5px;top:-5px} .ui-resizable-ne{cursor:ne-resize;width:9px;height:9px;right:-5px;top:-5px}
/* cache key: enwiki:resourceloader:filter:minify-css:7:6edb0b5932c338be8f0957237aa57681 */.ui-button{display:inline-block;position:relative;padding:0;margin-right:.1em;text-decoration:none !important;cursor:pointer;text-align:center;zoom:1;overflow:visible} .ui-button-icon-only{width:2.2em} button.ui-button-icon-only{width:2.4em} .ui-button-icons-only{width:3.4em}button.ui-button-icons-only{width:3.7em} .ui-button .ui-button-text{display:block;line-height:1.4}.ui-button-text-only .ui-button-text{padding:0.3em 1em 0.25em 1em}.ui-button-icon-only .ui-button-text,.ui-button-icons-only .ui-button-text{padding:0.3em;text-indent:-9999999px}.ui-button-text-icon-primary .ui-button-text,.ui-button-text-icons .ui-button-text{padding:0.3em 1em 0.25em 2.1em}.ui-button-text-icon-secondary .ui-button-text,.ui-button-text-icons .ui-button-text{padding:0.3em 2.1em 0.25em 1em}.ui-button-text-icons .ui-button-text{padding-left:2.1em;padding-right:2.1em} input.ui-button{padding:0.3em 1em} .ui-button-icon-only .ui-icon,.ui-button-text-icon-primary .ui-icon,.ui-button-text-icon-secondary .ui-icon,.ui-button-text-icons .ui-icon,.ui-button-text-icon .ui-icon,.ui-button-icons-only .ui-icon{position:absolute;top:50%;margin-top:-9px}.ui-button-icon-only .ui-icon{left:50%;margin-left:-8px}.ui-button-text-icon-primary .ui-button-icon-primary,.ui-button-text-icon .ui-button-icon-primary,.ui-button-text-icons .ui-button-icon-primary,.ui-button-icons-only .ui-button-icon-primary{left:0.5em}.ui-button-text-icon-secondary .ui-button-icon-secondary,.ui-button-text-icon .ui-button-icon-secondary,.ui-button-text-icons .ui-button-icon-secondary,.ui-button-icons-only .ui-button-icon-secondary{right:0.5em} .ui-buttonset{margin-right:7px}.ui-buttonset .ui-button{margin-left:0;margin-right:-.3em} button.ui-button::-moz-focus-inner{border:0;padding:0} body .ui-button{margin:0.5em 0 0.5em 0.4em;border:1px solid #a6a6a6 !important;background:#f2f2f2 url() repeat-x scroll 50% 100% !important;background:#f2f2f2 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-off.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie;cursor:pointer;font-size:1em;line-height:1.4em;width:auto;overflow:visible}  .ui-button.ui-corner-all,.ui-button.ui-corner-top,.ui-button.ui-corner-left,.ui-button.ui-corner-tl{-moz-border-radius-topleft:4px;-webkit-border-top-left-radius:4px;border-top-left-radius:4px}.ui-button.ui-corner-all,.ui-button.ui-corner-top,.ui-button.ui-corner-right,.ui-button.ui-corner-tr{-moz-border-radius-topright:4px;-webkit-border-top-right-radius:4px;border-top-right-radius:4px}.ui-button.ui-corner-all,.ui-button.ui-corner-bottom,.ui-button.ui-corner-left,.ui-button.ui-corner-bl{-moz-border-radius-bottomleft:4px;-webkit-border-bottom-left-radius:4px;border-bottom-left-radius:4px}.ui-button.ui-corner-all,.ui-button.ui-corner-bottom,.ui-button.ui-corner-right,.ui-button.ui-corner-br{-moz-border-radius-bottomright:4px;-webkit-border-bottom-right-radius:4px;border-bottom-right-radius:4px}body .ui-button:hover{border-color:#6e7273;background:#e1e1e1 url() repeat-x scroll 50% 100% !important;background:#e1e1e1 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-over.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button:active,body .ui-button:focus{border-color:#707271;background:#bfbfbf url() repeat-x scroll 50% 100% !important;background:#bfbfbf url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-down.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.disabled{color:#7f7f7f;border-color:#cccccc;background:#f2f2f2 url() repeat-x scroll 50% 100% !important;background:#f2f2f2 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-disabled.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie} body button.ui-button::-moz-focus-inner{border:0} body .ui-button-large{padding:5px} .ui-button-green .ui-icon,.ui-button-blue .ui-icon,.ui-button-red .ui-icon,.ui-button-orange .ui-icon{background-image:url() !important;background-image:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/ui-icons_ffffff_256x240.png?2013-01-02T16:11:40Z) !important!ie} body .ui-button.ui-button-green{color:white !important;border-color:#97af7e !important;background:#3cb677 url() repeat-x scroll 50% 100% !important;background:#3cb677 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-green.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-green:hover{border-color:#778e61 !important;background:#339b65 url() repeat-x scroll 50% 100% !important;background:#339b65 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-green-hover.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-green.ui-button-large{background:#3cb677 url() repeat-x scroll 50% 100% !important;background:#3cb677 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-green-large.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-green.ui-button-large:hover{background:#339b65 url() repeat-x scroll 50% 100% !important;background:#339b65 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-green-hover-large.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-green.disabled{filter:alpha(opacity=50);-moz-opacity:0.50;-khtml-opacity:0.50;opacity:0.50} body .ui-button.ui-button-blue{color:white !important;border-color:#628acb !important;background:#3365ba url() repeat-x scroll 50% 100% !important;background:#3365ba url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-blue.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-blue:hover{border-color:#5375ad !important;background:#2b569e url() repeat-x scroll 50% 100% !important;background:#2b569e url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-blue-hover.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-blue.ui-button-large{background:#3365ba url() repeat-x scroll 50% 100% !important;background:#3365ba url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-blue-large.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-blue.ui-button-large:hover{background:#2b569e url() repeat-x scroll 50% 100% !important;background:#2b569e url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-blue-hover-large.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-blue.disabled{filter:alpha(opacity=50);-moz-opacity:0.50;-khtml-opacity:0.50;opacity:0.50} body .ui-button.ui-button-red{color:white !important;border-color:#af977e !important;background:#cb0000 url() repeat-x scroll 50% 100% !important;background:#cb0000 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-red.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-red:hover{border-color:#8e7761 !important;background:#ad0000 url() repeat-x scroll 50% 100% !important;background:#ad0000 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-red-hover.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-red.ui-button-large{background:#cb0000 url() repeat-x scroll 50% 100% !important;background:#cb0000 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-red.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-red.ui-button-large:hover{background:#ad0000 url() repeat-x scroll 50% 100% !important;background:#ad0000 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-red-hover.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-red.disabled{filter:alpha(opacity=50);-moz-opacity:0.50;-khtml-opacity:0.50;opacity:0.50} body .ui-button.ui-button-orange{color:white !important;border-color:#f3a863 !important;background:#f07f14 url() repeat-x scroll 50% 100% !important;background:#f07f14 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-orange.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-orange:hover{border-color:#ce9055 !important;background:#cc6c11 url() repeat-x scroll 50% 100% !important;background:#cc6c11 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-orange-hover.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-orange.ui-button-large{background:#f07f14 url() repeat-x scroll 50% 100% !important;background:#f07f14 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-orange-large.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-orange.ui-button-large:hover{background:#cc6c11 url() repeat-x scroll 50% 100% !important;background:#cc6c11 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/button-orange-hover-large.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie}body .ui-button.ui-button-orange.disabled{filter:alpha(opacity=50);-moz-opacity:0.50;-khtml-opacity:0.50;opacity:0.50}
/* cache key: enwiki:resourceloader:filter:minify-css:7:9d8f7e3cdef4cd895bd8cfea2cfc79a8 */.ui-dialog{position:absolute;padding:0;width:300px}.ui-dialog .ui-dialog-titlebar{padding:.75em;position:relative}.ui-dialog .ui-dialog-title{float:left;margin:0}.ui-dialog .ui-dialog-titlebar-close{position:absolute;right:.75em;top:50%;width:19px;margin:-10px 0 0 0;padding:1px;height:18px}.ui-dialog .ui-dialog-titlebar-close span{display:block;margin:1px}.ui-dialog .ui-dialog-titlebar-close:hover,.ui-dialog .ui-dialog-titlebar-close:focus{padding:0}.ui-dialog .ui-dialog-content{border:0;padding:.5em 1em;background:none;overflow:auto;zoom:1}.ui-dialog .ui-dialog-buttonpane{text-align:left;border-width:1px 0 0 0;background-image:none;margin:.5em 0 0 0;padding:.3em 1em .5em .4em}.ui-dialog .ui-dialog-buttonpane .ui-dialog-buttonset{float:right}.ui-dialog .ui-resizable-se{width:14px;height:14px;right:3px;bottom:3px}.ui-draggable .ui-dialog-titlebar{cursor:move} body .ui-dialog .ui-dialog-titlebar-close:hover{text-decoration:none}body .ui-dialog .ui-dialog-content .status-invalid input{border:2px solid red;padding:2px 1px}body .ui-dialog .ui-dialog-titlebar{padding:0.9em 1.4em 0.6em !important}body .ui-dialog .ui-widget-header{background:#f0f0f0 url() repeat-x scroll 50% 100% !important;background:#f0f0f0 url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/titlebar-fade.png?2013-01-02T16:11:40Z) repeat-x scroll 50% 100% !important!ie} body .ui-dialog .ui-icon-closethick{background:url() no-repeat 50% 50% !important;background:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.ui/themes/vector/images/close.png?2013-01-02T16:11:40Z) no-repeat 50% 50% !important!ie}body .ui-dialog .ui-dialog-buttonpane{margin-top:0 !important;padding:0.3em 1.4em 0.5em 1.4em !important}
/* cache key: enwiki:resourceloader:filter:minify-css:7:eba770319cbc03663015cf58c11d8806 */.wp-teahouse-question-form{position:absolute;margin-left:auto;margin-right:auto;background-color:#f4f3f0;border:1px solid #a7d7f9;padding:1em}#wp-th-question-ask{float:right}.wp-teahouse-ask a.external{background-image:none !important}.wp-teahouse-respond-form{position:absolute;margin-left:auto;margin-right:auto;background-color:#f4f3f0;border:1px solid #a7d7f9;padding:1em}.wp-th-respond{float:right}.wp-teahouse-respond a.external{background-image:none !important}
/* cache key: enwiki:resourceloader:filter:minify-css:7:ba4e3603af357b5172e85672664d39a8 */.PopUpMediaTransform a .play-btn-large{position :absolute;top:50%;left :50%;width:70px;height:53px;margin-left:-35px;margin-top:-25px;background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/TimedMediaHandler/resources/player_big_play_button.png?2013-01-02T19:40:00Z)!ie}.PopUpMediaTransform a .play-btn-large :hover{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/TimedMediaHandler/resources/player_big_play_button_hover.png?2013-01-02T19:40:00Z)!ie}.PopUpMediaTransform{position :relative;display:inline-block}li.gallerybox div.thumb div.PopUpMediaTransform{margin:0 auto}
/* cache key: enwiki:resourceloader:filter:minify-css:7:daf2e07626c3c28579f2d2b13af3df60 */.tipsy{padding:5px;position:absolute;z-index:100000;cursor:default}.tipsy-inner{padding:5px 8px 4px 8px; background-color:#ffffff;border:solid 1px #a7d7f9;color:black;max-width:15em;border-radius:4px;-moz-border-radius:4px;-webkit-border-radius:4px; }.tipsy-arrow{position:absolute;background:url() no-repeat top left;background:url(//bits.wikimedia.org/static-1.21wmf7/resources/jquery.tipsy/images/tipsy.png?2013-01-02T16:11:40Z) no-repeat top left!ie;width:11px;height:6px} .tipsy-n .tipsy-arrow{top:0px;left:50%;margin-left:-5px} .tipsy-nw .tipsy-arrow{top:1px;left:10px} .tipsy-ne .tipsy-arrow{top:1px;right:10px} .tipsy-s .tipsy-arrow{bottom:0px;left:50%;margin-left:-5px;background-position:bottom left} .tipsy-sw .tipsy-arrow{bottom:0px;left:10px;background-position:bottom left} .tipsy-se .tipsy-arrow{bottom:0px;right:10px;background-position:bottom left} .tipsy-e .tipsy-arrow{top:50%;margin-top:-5px;right:1px;width:5px;height:11px;background-position:top right} .tipsy-w .tipsy-arrow{top:50%;margin-top:-5px;left:0px;width:6px;height:11px}
/* cache key: enwiki:resourceloader:filter:minify-css:7:2dc36d38ffd3a1f2a40539893cbbd77a */.articleFeedback{position:relative;display:inline-block;margin-top:1em}@media print{.articleFeedback{display:none}}.articleFeedback-panel{background-color:#f9f9f9;border:1px solid #cccccc;padding-bottom:1px}.articleFeedback-error-message{padding:3em;text-align:center}.articleFeedback-error{display:none;position:absolute;top:0;bottom:0;left:0;right:0;background-color:#f9f9f9;border:1px solid #cccccc;padding-bottom:1px}.articleFeedback-lock{display:none;position:absolute;top:0;left:0;right:0}.articleFeedback-pitches{float:absolute;top:1;left:1;right:1;background-color:#f9f9f9}.articleFeedback-pitch{display:none}.articleFeedback-lock{background-color:transparent}.articleFeedback-pitch-or{margin-left:0.75em;margin-right:0.25em}.articleFeedback-reject{border:none;background-color:transparent;cursor:pointer;color:#0645AD;line-height:1.4em}.articleFeedback-reject:hover{text-decoration:underline}.articleFeedback-pitch .articleFeedback-buffer{padding:0.75em 1em}.articleFeedback-panel{float:left}.articleFeedback-panel .articleFeedback-buffer{padding:0.75em 1em}.articleFeedback-title{font-size:1.4em}.articleFeedback-pitch .articleFeedback-title{font-size:1em;padding-left:28px;line-height:32px;background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/success.png?2013-01-02T19:36:40Z)!ie;background-repeat:no-repeat;background-position:left center;margin-bottom:0.5em}.articleFeedback-pitch .articleFeedback-pop{padding:1em;margin:0;background-color:white;border:solid 1px silver; -webkit-border-radius:5px;-moz-border-radius:5px;border-radius:5px}.articleFeedback-message{margin:0.33em;font-size:1.5em}.articleFeedback-body{margin:0.5em;color:#333333}.articleFeedback-switch{cursor:pointer;color:#0645AD;float:right;line-height:1.4em;background-repeat:no-repeat;background-position:right center;padding-right:22px}.articleFeedback-switch:hover{text-decoration:underline}.articleFeedback-switch-form{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/form.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-switch-report{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/report.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-switch-form:hover{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/form-hover.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-switch-report:hover{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/report-hover.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-explanation,.articleFeedback-description{float:left;font-weight:bold;margin-bottom:0.75em}.articleFeedback-rating-labels{margin-left:10px}.articleFeedback-rating-label,.articleFeedback-rating-clear{float:left;height:21px;width:21px;background-repeat:no-repeat;background-position:center center;cursor:pointer}.articleFeedback-rating-label{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/star-empty.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-rating-clear{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/trash.png?2013-01-02T19:36:40Z)!ie;display:none}.articleFeedback-rating-labels:hover .articleFeedback-rating-clear{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/trash-hover.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-rating-label.articleFeedback-rating-label-full{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/star-full.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-expired .articleFeedback-rating-label.articleFeedback-rating-label-full{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/star-full-expired.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-rating-new .articleFeedback-rating-label.articleFeedback-rating-label-full,.articleFeedback-rating .articleFeedback-rating-label.articleFeedback-rating-label-hover-tail{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/star-new.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-rating .articleFeedback-rating-label.articleFeedback-rating-label-hover-head{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/star-new-hover.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-rating-new .articleFeedback-rating-label.articleFeedback-rating-label-down{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/star-new-down.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-rating-tooltip{float:left;width:12em;margin-left:12px;color:#999999;font-size:0.9em;display:none}.articleFeedback-rating{float:left;width:11em;height:5em;margin-bottom:0.5em}.articleFeedback-rating-average{float:left;margin-right:0.5em;width:2em;text-align:right;font-size:0.8em;line-height:17px}.articleFeedback-rating-meter{float:left;height:17px;width:104px;border:solid 1px #cccccc;border-radius:3px;background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/segment-empty.png?2013-01-02T19:36:40Z)!ie;background-repeat:repeat-x;background-position:center left;overflow:hidden}.articleFeedback-rating-meter div{float:left;height:17px;background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/segment-full.png?2013-01-02T19:36:40Z)!ie;background-repeat:repeat-x;background-position:center left}.articleFeedback-rating-count{float:right;font-size:0.8em;color:#999999;cursor:default;margin-right:1em}.articleFeedback-label{cursor:pointer;padding-left:20px;background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/question.png?2013-01-02T19:36:40Z)!ie;background-repeat:no-repeat;background-position:center left}.articleFeedback-label:hover{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/question-hover.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-submit{float:right}.articleFeedback-expertise-disabled,.articleFeedback-helpimprove-disabled{color:silver}.articleFeedback-expertise{float:left;margin-bottom:0.5em;margin-top:0.75em}.articleFeedback-expertise input{float:left;margin-bottom:0.5em;clear:both;cursor:pointer}.articleFeedback-expertise label{margin-left:0.5em;margin-bottom:0.5em;float:left;line-height:1.4em;cursor:pointer}.articleFeedback-expertise-options{clear:both;display:none}.articleFeedback-expertise-options input{display:block;clear:both;margin-left:2em}.articleFeedback-expertise-options label{line-height:1.6em}.articleFeedback-expertise-options .articleFeedback-helpimprove-email{width:20em;margin-left:4em;margin-top:0.25em;cursor:text}.articleFeedback-helpimprove-note{margin-left:4em;font-size:0.8em;clear:both}.articleFeedback-helpimprove-email.valid{background-color:#C0FFC0}.articleFeedback-helpimprove-email.invalid{background-color:#FFC0C0}.articleFeedback-pending,.articleFeedback-success{float:right}.articleFeedback-pending span,.articleFeedback-success span{display:none;padding:12px 12px 12px 28px;font-size:0.8em;line-height:3.6em;background-repeat:no-repeat;background-position:center left;color:green}.articleFeedback-pending span{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/attention.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-success span{background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/success.png?2013-01-02T19:36:40Z)!ie}.articleFeedback-expiry{display:none;border:solid 1px orange;background-color:white;padding:0.5em}.articleFeedback-expiry-title{font-size:1.2em;padding-left:28px;background-image:url();background-image:url(//bits.wikimedia.org/static-1.21wmf7/extensions/ArticleFeedback/modules/jquery.articleFeedback/images/alert.png?2013-01-02T19:36:40Z)!ie;background-repeat:no-repeat;background-position:center left}.articleFeedback-expiry-message{padding-left:28px;color:#777777}
/* cache key: enwiki:resourceloader:filter:minify-css:7:ea1f9030541ae79ff4f75ff22064d8f1 */</style><meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" href="WikipediaBurrows%E2%80%93Wheeler_transform_files/load.css">
<style>a:lang(ar),a:lang(ckb),a:lang(fa),a:lang(kk-arab),a:lang(mzn),a:lang(ps),a:lang(ur){text-decoration:none}
/* cache key: enwiki:resourceloader:filter:minify-css:7:d11e4771671c2d6cdedf7c90d8131cd5 */</style>

<script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_010.php"></script><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load.php"></script><style title="spinjs"></style>
<script>if(window.mw){
mw.config.set({"wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Burrows–Wheeler_transform","wgTitle":"Burrows–Wheeler transform","wgCurRevisionId":526993356,"wgArticleId":36777,"wgIsArticle":true,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Wikipedia articles needing copy edit from September 2012","All articles needing copy edit","All articles with unsourced statements","Articles with unsourced statements from September 2012","Lossless compression algorithms","Transforms","Articles with example pseudocode","Articles with example Python code"],"wgBreakFrames":false,"wgPageContentLanguage":"en","wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgMonthNamesShort":["","Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"],"wgRelevantPageName":"Burrows–Wheeler_transform","wgRestrictionEdit":[],"wgRestrictionMove":[],"wgVectorEnabledModules":{"collapsiblenav":true,"collapsibletabs":true,"editwarning":true,"expandablesearch":false,"footercleanup":true,"sectioneditlinks":false,"experiments":true},"wgWikiEditorEnabledModules":{"toolbar":true,"dialogs":true,"hidesig":true,"templateEditor":false,"templates":false,"preview":false,"previewDialog":false,"publish":false,"toc":false},"wgTrackingToken":"ddbeb4b85724d90704e89afcb633b6e5","wgArticleFeedbackv5Permissions":{"aft-reader":true,"aft-member":false,"aft-editor":false,"aft-monitor":false,"aft-administrator":false,"aft-oversighter":false},"wgVisualEditor":{"isPageWatched":false,"enableSectionEditLinks":false},"wikilove-recipient":"","wikilove-anon":0,"mbEmailEnabled":true,"mbUserEmail":false,"mbIsEmailConfirmationPending":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1,"quality":2,"pristine":3}}},"wgStableRevisionId":null,"wgCategoryTreePageCategoryOptions":"{\"mode\":0,\"hideprefix\":20,\"showcount\":true,\"namespaces\":false}","Geo":{"city":"","country":""},"wgNoticeProject":"wikipedia","aftv5Article":{"id":36777,"title":"Burrows–Wheeler transform","namespace":0,"categories":["All articles needing copy edit","All articles with unsourced statements","Articles with example Python code","Articles with example pseudocode","Articles with unsourced statements from September 2012","Lossless compression algorithms","Transforms","Wikipedia articles needing copy edit from September 2012"],"permissionLevel":"aft-reader"}});
}</script><script>if(window.mw){
mw.loader.implement("user.options",function(){mw.user.options.set({"ccmeonemails":0,"cols":80,"date":"default","diffonly":0,"disablemail":0,"disablesuggest":0,"editfont":"default","editondblclick":0,"editsection":1,"editsectiononrightclick":0,"enotifminoredits":0,"enotifrevealaddr":0,"enotifusertalkpages":1,"enotifwatchlistpages":0,"extendwatchlist":0,"externaldiff":0,"externaleditor":0,"fancysig":0,"forceeditsummary":0,"gender":"unknown","hideminor":0,"hidepatrolled":0,"imagesize":2,"justify":0,"math":0,"minordefault":0,"newpageshidepatrolled":0,"nocache":0,"noconvertlink":0,"norollbackdiff":0,"numberheadings":0,"previewonfirst":0,"previewontop":1,"quickbar":5,"rcdays":7,"rclimit":50,"rememberpassword":0,"rows":25,"searchlimit":20,"showhiddencats":false,"showjumplinks":1,"shownumberswatching":1,"showtoc":1,"showtoolbar":1,"skin":"vector","stubthreshold":0,"thumbsize":4,"underline":2,"uselivepreview":0,"usenewrc":0,"watchcreations":1,"watchdefault":0,"watchdeletion":0,"watchlistdays":3
,"watchlisthideanons":0,"watchlisthidebots":0,"watchlisthideliu":0,"watchlisthideminor":0,"watchlisthideown":0,"watchlisthidepatrolled":0,"watchmoves":0,"wllimit":250,"flaggedrevssimpleui":1,"flaggedrevsstable":0,"flaggedrevseditdiffs":true,"flaggedrevsviewdiffs":false,"vector-simplesearch":1,"useeditwarning":1,"vector-collapsiblenav":1,"usebetatoolbar":1,"usebetatoolbar-cgd":1,"aftv5-last-filter":null,"wikilove-enabled":1,"echo-email-notificationspagetriage-mark-as-reviewed":true,"echo-email-notificationspagetriage-add-maintenance-tag":true,"echo-email-notificationspagetriage-add-deletion-tag":true,"ep_showtoplink":false,"ep_bulkdelorgs":false,"ep_bulkdelcourses":true,"ep_showdyk":true,"variant":"en","language":"en","searchNs0":true,"searchNs1":false,"searchNs2":false,"searchNs3":false,"searchNs4":false,"searchNs5":false,"searchNs6":false,"searchNs7":false,"searchNs8":false,"searchNs9":false,"searchNs10":false,"searchNs11":false,"searchNs12":false,"searchNs13":false,"searchNs14":false
,"searchNs15":false,"searchNs100":false,"searchNs101":false,"searchNs108":false,"searchNs109":false,"searchNs446":false,"searchNs447":false,"searchNs710":false,"searchNs711":false,"gadget-teahouse":1,"gadget-ReferenceTooltips":1,"gadget-HotCat":1,"gadget-DRN-wizard":1,"gadget-charinsert":1,"gadget-mySandbox":1});;},{},{});mw.loader.implement("user.tokens",function(){mw.user.tokens.set({"editToken":"+\\","patrolToken":false,"watchToken":false});;},{},{});
/* cache key: enwiki:resourceloader:filter:minify-js:7:19e64e7d3e84450cdd6aaeece6e56fab */
}</script>
<script>if(window.mw){
mw.loader.load(["mediawiki.page.startup","mediawiki.legacy.wikibits","mediawiki.legacy.ajax","ext.vector.footerCleanup","ext.wikimediaShopLink.core","ext.centralNotice.bannerController"]);
}</script><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_003.php"></script><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_004.php"></script>
<style type="text/css">/*<![CDATA[*/
.source-python {line-height: normal;}
.source-python li, .source-python pre {
	line-height: normal; border: 0px none white;
}
/**
 * GeSHi Dynamically Generated Stylesheet
 * --------------------------------------
 * Dynamically generated stylesheet for python
 * CSS class: source-python, CSS id: 
 * GeSHi (C) 2004 - 2007 Nigel McNie, 2007 - 2008 Benny Baumann
 * (http://qbnz.com/highlighter/ and http://geshi.org/)
 * --------------------------------------
 */
.python.source-python .de1, .python.source-python .de2 {font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;}
.python.source-python  {font-family:monospace;}
.python.source-python .imp {font-weight: bold; color: red;}
.python.source-python li, .python.source-python .li1 {font-weight: normal; vertical-align:top;}
.python.source-python .ln {width:1px;text-align:right;margin:0;padding:0 2px;vertical-align:top;}
.python.source-python .li2 {font-weight: bold; vertical-align:top;}
.python.source-python .kw1 {color: #ff7700;font-weight:bold;}
.python.source-python .kw2 {color: #008000;}
.python.source-python .kw3 {color: #dc143c;}
.python.source-python .kw4 {color: #0000cd;}
.python.source-python .co1 {color: #808080; font-style: italic;}
.python.source-python .coMULTI {color: #808080; font-style: italic;}
.python.source-python .es0 {color: #000099; font-weight: bold;}
.python.source-python .br0 {color: black;}
.python.source-python .sy0 {color: #66cc66;}
.python.source-python .st0 {color: #483d8b;}
.python.source-python .nu0 {color: #ff4500;}
.python.source-python .me1 {color: black;}
.python.source-python .ln-xtra, .python.source-python li.ln-xtra, .python.source-python div.ln-xtra {background-color: #ffc;}
.python.source-python span.xtra { display:block; }

/*]]>*/
</style><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/geoiplookup"></script><link rel="dns-prefetch" href="http://meta.wikimedia.org/"><!--[if lt IE 7]><style type="text/css">body{behavior:url("/w/skins-1.21wmf7/vector/csshover.min.htc")}</style><![endif]--><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_006.php" async=""></script><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_007.php" async=""></script><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_008.php" async=""></script><script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_002.php" async=""></script></head>
<body class="mediawiki ltr sitedir-ltr ns-0 ns-subject page-Burrows–Wheeler_transform skin-vector action-view vector-animateLayout">
		<div id="mw-page-base" class="noprint"></div>
		<div id="mw-head-base" class="noprint"></div>
		<!-- content -->
		<div id="content" class="mw-body" role="main">
			<a id="top"></a>
			<div id="mw-js-message" style="display:none;"></div>
						<!-- sitenotice -->
			<div id="siteNotice"><div class="cn-default" id="centralNotice"><style type="text/css">

#centralNotice.collapsed #voy5g {
  display: none;
 }

#voy5g #cn-close-box {
  position: absolute;
  z-index: 98;
  top: 0px;
  right: 0px;
  padding: 0px 3px 20px 20px;
 }

#voy5g {
  border: solid 1px #ddd; 
  position: relative;
  overflow: hidden;
  margin-bottom: 0.5em !important;
}

#voy5g-content {
  position:relative;
  padding: 14px 0 12px 200px;
  text-align: center;
  font-family: sans,sans-serif;
  font-size:   1.2em;
  line-height: 1.5em;
}

#voy5g-logo {
  position: absolute;
  background-position: 60px 5px;
  background-image: url("//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Wikivoyage-logo.svg/120px-Wikivoyage-logo.svg.png");
  background-repeat: no-repeat;
  height: 200px;
  width:  200px;
}

#voy5g a {
  text-decoration: none;
}

#voy5g-content:hover {
  text-decoration: underline;
}

</style>

<div id="voy5g">
  <a class="cn-full-banner-click" href="http://www.wikivoyage.org/">
  <div id="voy5g-logo"> </div>
  <div id="voy5g-content">
      <div>This week we are launching <b>Wikivoyage</b>.<br>Join us in creating a free travel guide that anyone can edit.</div>
  </div>
 </a>

  <div id="cn-close-box">
    <a href="#" title="Close" onclick="hideBanner();return false;"><img src="WikipediaBurrows%E2%80%93Wheeler_transform_files/closewindow.png" alt="Close" border="0" height="13" width="13"></a>
  </div>
</div></div><!-- CentralNotice --><script>
	mw.loader.using( 'ext.centralNotice.bannerController', function() { mw.centralNotice.initialize(); } );
</script>
</div>
			<!-- /sitenotice -->
						<!-- firstHeading -->
			<h1 id="firstHeading" class="firstHeading" lang="en"><span dir="auto">Burrows–Wheeler transform</span></h1>
			<!-- /firstHeading -->
			<!-- bodyContent -->
			<div id="bodyContent">
								<!-- tagline -->
				<div id="siteSub">From Wikipedia, the free encyclopedia</div>
				<!-- /tagline -->
								<!-- subtitle -->
				<div id="contentSub"></div>
				<!-- /subtitle -->
																<!-- jumpto -->
				<div id="jump-to-nav" class="mw-jump">
					Jump to:					<a href="#mw-head">navigation</a>, 					<a href="#p-search">search</a>
				</div>
				<!-- /jumpto -->
								<!-- bodycontent -->
				<div id="mw-content-text" dir="ltr" class="mw-content-ltr" lang="en"><p>The <b>Burrows–Wheeler transform</b> (<b>BWT</b>, also called <b>block-sorting compression</b>), is an <a href="http://en.wikipedia.org/wiki/Algorithm" title="Algorithm">algorithm</a> used in <a href="http://en.wikipedia.org/wiki/Data_compression" title="Data compression">data compression</a> techniques such as <a href="http://en.wikipedia.org/wiki/Bzip2" title="Bzip2">bzip2</a>. It was invented by <a href="http://en.wikipedia.org/wiki/Michael_Burrows" title="Michael Burrows">Michael Burrows</a> and <a href="http://en.wikipedia.org/wiki/David_Wheeler_%28computer_scientist%29" title="David Wheeler (computer scientist)">David Wheeler</a> in 1994 while working at <a href="http://en.wikipedia.org/wiki/DEC_Systems_Research_Center" title="DEC Systems Research Center">DEC Systems Research Center</a> in <a href="http://en.wikipedia.org/wiki/Palo_Alto" title="Palo Alto" class="mw-redirect">Palo Alto</a>, California.<sup id="cite_ref-Burrows1994_1-0" class="reference"><a href="#cite_note-Burrows1994-1"><span>[</span>1<span>]</span></a></sup> It is based on a previously unpublished transformation discovered by Wheeler in 1983.</p>
<p>When a <a href="http://en.wikipedia.org/wiki/Character_string_%28computer_science%29" title="Character string (computer science)" class="mw-redirect">character string</a> is transformed by the BWT, none of its characters change value. The transformation <a href="http://en.wikipedia.org/wiki/Permutation" title="Permutation">permutes</a>
 the order of the characters. If the original string had several 
substrings that occurred often, then the transformed string will have 
several places where a single character is repeated multiple times in a 
row. This is useful for compression, since it tends to be easy to 
compress a string that has runs of repeated characters by techniques 
such as <a href="http://en.wikipedia.org/wiki/Move-to-front_transform" title="Move-to-front transform">move-to-front transform</a> and <a href="http://en.wikipedia.org/wiki/Run-length_encoding" title="Run-length encoding">run-length encoding</a>.</p>
<p>For example:</p>
<table class="wikitable">
<tbody><tr>
<th>Input</th>
<td><tt>SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES</tt></td>
</tr>
<tr>
<th>Output</th>
<td><tt>TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT</tt></td>
</tr>
</tbody></table>
<p>The output is easier to compress because it has many repeated 
characters. In fact, in the transformed string, there are a total of six
 runs of identical characters: <tt>XX</tt>, <tt>SS</tt>, <tt>PP</tt>, <tt>..</tt>, <tt>II</tt>, and <tt>III</tt>, which together make 13 out of the 44 characters in it.</p>
<table id="toc" class="toc">
<tbody><tr>
<td>
<div id="toctitle">
<h2>Contents</h2>
<span class="toctoggle">&nbsp;[<a href="#" class="internal" id="togglelink">hide</a>]&nbsp;</span></div>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#Example"><span class="tocnumber">1</span> <span class="toctext">Example</span></a></li>
<li class="toclevel-1 tocsection-2"><a href="#Optimization"><span class="tocnumber">2</span> <span class="toctext">Optimization</span></a></li>
<li class="toclevel-1 tocsection-3"><a href="#Bijective_variant"><span class="tocnumber">3</span> <span class="toctext">Bijective variant</span></a></li>
<li class="toclevel-1 tocsection-4"><a href="#Dynamic_Burrows.E2.80.93Wheeler_transform"><span class="tocnumber">4</span> <span class="toctext">Dynamic Burrows–Wheeler transform</span></a></li>
<li class="toclevel-1 tocsection-5"><a href="#Sample_implementation"><span class="tocnumber">5</span> <span class="toctext">Sample implementation</span></a></li>
<li class="toclevel-1 tocsection-6"><a href="#BWT_in_bioinformatics"><span class="tocnumber">6</span> <span class="toctext">BWT in bioinformatics</span></a></li>
<li class="toclevel-1 tocsection-7"><a href="#References"><span class="tocnumber">7</span> <span class="toctext">References</span></a></li>
<li class="toclevel-1 tocsection-8"><a href="#External_links"><span class="tocnumber">8</span> <span class="toctext">External links</span></a></li>
</ul>
</td>
</tr>
</tbody></table>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=1" title="Edit section: Example">edit</a>]</span> <span class="mw-headline" id="Example">Example</span></h2>
<p>The transform is done by <a href="http://en.wikipedia.org/wiki/Sorting" title="Sorting">sorting</a> all rotations of the text in <a href="http://en.wikipedia.org/wiki/Lexicographic_order" title="Lexicographic order" class="mw-redirect">lexicographic order</a>, then taking the last column. For example, the text "^BANANA<span style="color:red;">|</span>" is transformed into "BNN^AA<span style="color:red;">|</span>A" through these steps (the red <span style="color:red;">|</span> character indicates the '<a href="http://en.wikipedia.org/wiki/End-of-file" title="End-of-file">EOF</a>' pointer):</p>
<table class="wikitable">
<tbody><tr>
<th colspan="5">Transformation</th>
</tr>
<tr>
<th>Input</th>
<th>All<br>
Rotations</th>
<th>Sorting All Rows in Alphabetical<br>
Order by their first letters</th>
<th>Taking<br>
Last Column</th>
<th>Output<br>
Last Column</th>
</tr>
<tr>
<td align="center">
<pre>^BANANA<span style="color:red;">|</span>
</pre></td>
<td>
<pre>^BANANA<span style="color:red;">|</span>
<span style="color:red;">|</span>^BANANA
A<span style="color:red;">|</span>^BANAN
NA<span style="color:red;">|</span>^BANA
ANA<span style="color:red;">|</span>^BAN
NANA<span style="color:red;">|</span>^BA
ANANA<span style="color:red;">|</span>^B
BANANA<span style="color:red;">|</span>^
</pre></td>
<td>
<pre><b>A</b>NANA<span style="color:red;">|</span>^B
<b>A</b>NA<span style="color:red;">|</span>^BAN
<b>A</b><span style="color:red;">|</span>^BANAN
<b>B</b>ANANA<span style="color:red;">|</span>^
<b>N</b>ANA<span style="color:red;">|</span>^BA
<b>N</b>A<span style="color:red;">|</span>^BANA
<b>^</b>BANANA<span style="color:red;">|</span>
<span style="color:red;"><b>|</b></span>^BANANA
</pre></td>
<td>
<pre>ANANA<span style="color:red;">|</span>^<b>B</b>
ANA<span style="color:red;">|</span>^BA<b>N</b>
A<span style="color:red;">|</span>^BANA<b>N</b>
BANANA<span style="color:red;">|</span><b>^</b>
NANA<span style="color:red;">|</span>^B<b>A</b>
NA<span style="color:red;">|</span>^BAN<b>A</b>
^BANANA<span style="color:red;"><b>|</b></span>
<span style="color:red;">|</span>^BANAN<b>A</b>
</pre></td>
<td>
<pre>BNN^AA<span style="color:red;">|</span>A
</pre></td>
</tr>
</tbody></table>
<p>The following <a href="http://en.wikipedia.org/wiki/Pseudocode" title="Pseudocode">pseudocode</a> gives a simple (though inefficient) way to calculate the BWT and its inverse. It assumes that the input string <code>s</code> contains a special character 'EOF' which is the last character, occurs nowhere else in the text, and is ignored during sorting.</p>
<pre> <b>function</b> BWT (<i>string</i> s)
   create a table, rows are all possible rotations of s
   sort rows alphabetically
   return (last column of the table)
 
 <b>function</b> inverseBWT (<i>string</i> s)
   create empty table 
       
   <b>repeat</b> length(s) <b>times</b>
       insert s as a column of table before first column of the table   // first insert creates first column
       sort rows of the table alphabetically
   return (row that ends with the 'EOF' character)
</pre>
<p>To understand why this creates more-easily-compressible data, 
consider transforming a long English text frequently containing the word
 "the". Sorting the rotations of this text will often group rotations 
starting with "he " together, and the last character of that rotation 
(which is also the character before the "he ") will usually be "t", so 
the result of the transform would contain a number of "t" characters 
along with the perhaps less-common exceptions (such as if it contains 
"Brahe ") mixed in. So it can be seen that the success of this transform
 depends upon one value having a high probability of occurring before a 
sequence, so that in general it needs fairly long samples (a few 
kilobytes at least) of appropriate data (such as text).</p>
<p>The remarkable thing about the BWT is not that it generates a more 
easily encoded output—an ordinary sort would do that—but that it is <i>reversible</i>, allowing the original document to be re-generated from the last column data.</p>
<p>The inverse can be understood this way. Take the final table in the 
BWT algorithm, and erase all but the last column. Given only this 
information, you can easily reconstruct the first column. The last 
column tells you all the characters in the text, so just sort these 
characters alphabetically to get the first column. Then, the first and 
last columns (of each row) together give you all <i>pairs</i> of 
successive characters in the document, where pairs are taken cyclically 
so that the last and first character form a pair. Sorting the list of 
pairs gives the first <i>and second</i> columns. Continuing in this 
manner, you can reconstruct the entire list. Then, the row with the "end
 of file" character at the end is the original text. Reversing the 
example above is done like this:</p>
<table class="wikitable">
<tbody><tr>
<th colspan="4">Inverse Transformation</th>
</tr>
<tr>
<th colspan="4">Input</th>
</tr>
<tr>
<td colspan="4" align="center">
<pre>BNN^AA<span style="color:red;">|</span>A
</pre></td>
</tr>
<tr>
<th>Add 1</th>
<th>Sort 1</th>
<th>Add 2</th>
<th>Sort 2</th>
</tr>
<tr>
<td align="right">
<pre>B
N
N
^
A
A
<span style="color:red;">|</span>
A
</pre></td>
<td align="right">
<pre>A
A
A
B
N
N
^
<span style="color:red;">|</span>
</pre></td>
<td align="right">
<pre>BA
NA
NA
^B
AN
AN
<span style="color:red;">|</span>^
A<span style="color:red;">|</span>
</pre></td>
<td align="right">
<pre>AN
AN
A<span style="color:red;">|</span>
BA
NA
NA
^B
<span style="color:red;">|</span>^
</pre></td>
</tr>
<tr>
<th>Add 3</th>
<th>Sort 3</th>
<th>Add 4</th>
<th>Sort 4</th>
</tr>
<tr>
<td align="right">
<pre>BAN
NAN
NA<span style="color:red;">|</span>
^BA
ANA
ANA
<span style="color:red;">|</span>^B
A<span style="color:red;">|</span>^
</pre></td>
<td align="right">
<pre>ANA
ANA
A<span style="color:red;">|</span>^
BAN
NAN
NA<span style="color:red;">|</span>
^BA
<span style="color:red;">|</span>^B
</pre></td>
<td align="right">
<pre>BANA
NANA
NA<span style="color:red;">|</span>^
^BAN
ANAN
ANA<span style="color:red;">|</span>
<span style="color:red;">|</span>^BA
A<span style="color:red;">|</span>^B
</pre></td>
<td align="right">
<pre>ANAN
ANA<span style="color:red;">|</span>
A<span style="color:red;">|</span>^B
BANA
NANA
NA<span style="color:red;">|</span>^
^BAN
<span style="color:red;">|</span>^BA
</pre></td>
</tr>
<tr>
<th>Add 5</th>
<th>Sort 5</th>
<th>Add 6</th>
<th>Sort 6</th>
</tr>
<tr>
<td align="right">
<pre>BANAN
NANA<span style="color:red;">|</span>
NA<span style="color:red;">|</span>^B
^BANA
ANANA
ANA<span style="color:red;">|</span>^
<span style="color:red;">|</span>^BAN
A<span style="color:red;">|</span>^BA
</pre></td>
<td align="right">
<pre>ANANA
ANA<span style="color:red;">|</span>^
A<span style="color:red;">|</span>^BA
BANAN
NANA<span style="color:red;">|</span>
NA<span style="color:red;">|</span>^B
^BANA
<span style="color:red;">|</span>^BAN
</pre></td>
<td align="right">
<pre>BANANA
NANA<span style="color:red;">|</span>^
NA<span style="color:red;">|</span>^BA
^BANAN
ANANA<span style="color:red;">|</span>
ANA<span style="color:red;">|</span>^B
<span style="color:red;">|</span>^BANA
A<span style="color:red;">|</span>^BAN
</pre></td>
<td align="right">
<pre>ANANA<span style="color:red;">|</span>
ANA<span style="color:red;">|</span>^B
A<span style="color:red;">|</span>^BAN
BANANA
NANA<span style="color:red;">|</span>^
NA<span style="color:red;">|</span>^BA
^BANAN
<span style="color:red;">|</span>^BANA
</pre></td>
</tr>
<tr>
<th>Add 7</th>
<th>Sort 7</th>
<th>Add 8</th>
<th>Sort 8</th>
</tr>
<tr>
<td align="right">
<pre>BANANA<span style="color:red;">|</span>
NANA<span style="color:red;">|</span>^B
NA<span style="color:red;">|</span>^BAN
^BANANA
ANANA<span style="color:red;">|</span>^
ANA<span style="color:red;">|</span>^BA
<span style="color:red;">|</span>^BANAN
A<span style="color:red;">|</span>^BANA
</pre></td>
<td align="right">
<pre>ANANA<span style="color:red;">|</span>^
ANA<span style="color:red;">|</span>^BA
A<span style="color:red;">|</span>^BANA
BANANA<span style="color:red;">|</span>
NANA<span style="color:red;">|</span>^B
NA<span style="color:red;">|</span>^BAN
^BANANA
<span style="color:red;">|</span>^BANAN
</pre></td>
<td align="right">
<pre>BANANA<span style="color:red;">|</span>^
NANA<span style="color:red;">|</span>^BA
NA<span style="color:red;">|</span>^BANA
^BANANA<span style="color:red;">|</span>
ANANA<span style="color:red;">|</span>^B
ANA<span style="color:red;">|</span>^BAN
<span style="color:red;">|</span>^BANANA
A<span style="color:red;">|</span>^BANAN
</pre></td>
<td align="right">
<pre>ANANA<span style="color:red;">|</span>^B
ANA<span style="color:red;">|</span>^BAN
A<span style="color:red;">|</span>^BANAN
BANANA<span style="color:red;">|</span>^
NANA<span style="color:red;">|</span>^BA
NA<span style="color:red;">|</span>^BANA
^BANANA<span style="color:red;">|</span>
<span style="color:red;">|</span>^BANANA
</pre></td>
</tr>
<tr>
<th colspan="4">Output</th>
</tr>
<tr>
<td colspan="4" align="center">
<pre>^BANANA<span style="color:red;">|</span>
</pre></td>
</tr>
</tbody></table>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=2" title="Edit section: Optimization">edit</a>]</span> <span class="mw-headline" id="Optimization">Optimization</span></h2>
<p>A number of <a href="http://en.wikipedia.org/wiki/Optimization_%28computer_science%29" title="Optimization (computer science)" class="mw-redirect">optimizations</a>
 can make these algorithms run more efficiently without changing the 
output. In BWT, there is no need to represent the table in either the 
encoder or decoder. In the encoder, each row of the table can be 
represented by a single pointer into the strings, and the sort performed
 using the indices. Some care must be taken to ensure that the sort does
 not exhibit bad <a href="http://en.wikipedia.org/wiki/Best,_worst_and_average_case" title="Best, worst and average case">worst-case</a>
 behavior: Standard library sort functions are unlikely to be 
appropriate. In the decoder, there is also no need to store the table, 
and in fact no sort is needed at all. In time proportional to the 
alphabet size and string length, the decoded string may be generated one
 character at a time from right to left. A "character" in the algorithm 
can be a byte, or a bit, or any other convenient size.</p>
<p>There is no need to have an actual 'EOF' character. Instead, a 
pointer can be used that remembers where in a string the 'EOF' would be 
if it existed. In this approach, the output of the BWT must include both
 the transformed string, and the final value of the pointer. That means 
the BWT does expand its input slightly. The inverse transform then 
shrinks it back down to the original size: it is given a string and a 
pointer, and returns just a string.</p>
<p>A complete description of the algorithms can be found in Burrows and Wheeler's paper, or in a number of online sources.</p>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=3" title="Edit section: Bijective variant">edit</a>]</span> <span class="mw-headline" id="Bijective_variant">Bijective variant</span></h2>
<table class="metadata plainlinks ambox mbox-small-left ambox-style" style="">
<tbody><tr>
<td class="mbox-image"><a href="http://en.wikipedia.org/wiki/File:Acap.svg" class="image"><img alt="Acap.svg" src="WikipediaBurrows%E2%80%93Wheeler_transform_files/24px-Acap.png" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/52/Acap.svg/36px-Acap.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/52/Acap.svg/48px-Acap.svg.png 2x" height="27" width="24"></a></td>
<td class="mbox-text" style=""><span class="mbox-text-span">This section may require <a href="http://en.wikipedia.org/wiki/Wikipedia:Basic_copyediting" title="Wikipedia:Basic copyediting">copy-editing</a>. <small><i>(September 2012)</i></small></span></td>
</tr>
</tbody></table>
<p>When you do a BWTS or the BIJECTIVE BWT of ^BANANA you get ANNBAA^ you don't need a special character for the end of string<sup class="Template-Fact" style="white-space:nowrap;">[<i><a href="http://en.wikipedia.org/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources from September 2012">citation needed</span></a></i>]</sup>
 which forces one to increase character space by one or force one to 
have a separate field with a number value for an offset. Either one of 
these features makes compression harder. When dealing with short files 
the savings are large percent wise.</p>
<p>In the example above BWT changed ^BANANA| where | could be thought of as EOF but not in BNN^AA|A</p>
<p>Since that is not a valid file you would need to add something like BNN^AA|A| where the last | is true EOF</p>
<p>Thankfully for SMALL FILES BWTS would<br>
work on just the ^BANANA to get ANNBAA^<br>
then output to file would be ANNBAA^| where | is the True EOF</p>
<p>The fact is in the so-called normal BWT the first | was just<br>
a place holder for EOF and not the EOF<br>
So BNN^AA|A| would most likely either be written as<br>
BNN^AA (new symbol) A|<br>
or as<br>
(index field) BNN^AAA|<br>
which is why on VERY SHORT FILES you will have a hard time getting any compression with out using the bijective BWT<br>
On long files a lot depends on how the follow on compression pass is 
tuned. But in which case using the Bijective BWT or some version and 
there are many of BWT will likely only differ by a few bytes. Sometime 
one is shorter sometimes the other.</p>
<p>The bijective transform is done by <a href="http://en.wikipedia.org/wiki/Sorting" title="Sorting">sorting</a> all rotations of the <a href="http://en.wikipedia.org/wiki/Lyndon_word" title="Lyndon word">lyndon words</a>, in comparing two string of unequal length, we compare the infinite periodic repetitions of each of these,in <a href="http://en.wikipedia.org/wiki/Lexicographic_order" title="Lexicographic order" class="mw-redirect">lexicographic order</a>, then taking the last column of the base rotated lyndon word. For example, the text "^BANANA<span style="color:red;">|</span>" is transformed into "ANNBAA^<span style="color:red;">|</span>" through these steps (the red <span style="color:red;">|</span> character indicates the '<a href="http://en.wikipedia.org/wiki/End-of-file" title="End-of-file">EOF</a>' pointer) in original string:<br>
The EOF character is not Needed in the Bijective Transform so it is 
dropped during the Transform and added back in so that its in its proper
 place in the file.</p>
<p>First step break into lyndon words, in such a way that the words in the sequence are decreasing using comparison method above.<br>
"^BANANA" becomes (^) (B) (AN) (AN) (A) but with in change result I combine like Lydon words so I use (^) (B) (ANAN) (A)</p>
<table class="wikitable">
<tbody><tr>
<th colspan="5">Bijective Transformation</th>
</tr>
<tr>
<th>Input</th>
<th>All<br>
Rotations</th>
<th>Sorting All Rows in Alphabetical<br>
Order by their first letters</th>
<th>Taking Last Column<br>
of Rotated Lyndon word</th>
<th>Output<br>
Last Column</th>
</tr>
<tr>
<td align="center">
<pre>^BANANA<span style="color:red;">|</span>
</pre></td>
<td>
<pre>^^^^^^^^ (^)
<b>B</b>BBBBBBB (B)
<b>ANAN</b>ANAN... (ANAN)
<b>NANA</b>NANA... (NANA)
<b>ANAN</b>ANAN... (ANAN)
<b>NANA</b>NANA... (NANA)  
<b>A</b>AAAAAAA... (A)
</pre></td>
<td>
<pre><b>A</b>AAAAAAA... (A)
<b>A</b>NANANAN... (ANAN)
<b>A</b>NANANAN... (ANAN)
<b>B</b>BBBBBBB... (B)
<b>N</b>ANANANA... (NANA)
<b>N</b>ANANANA... (NANA)
<b>^</b>^^^^^^^... (^)
</pre></td>
<td>
<pre><b>A</b>AAAAAAA... (A)
ANA<b>N</b>ANAN... (ANAN)
ANA<b>N</b>ANAN... (ANAN)
<b>B</b>BBBBBBB... (B)
NAN<b>A</b>NANA... (NANA)
NAN<b>A</b>NANA... (NANA)
<b>^</b>^^^^^^^... (^)
</pre></td>
<td>
<pre>ANNBAA^<span style="color:red;">|</span>
</pre></td>
</tr>
</tbody></table>
<table class="wikitable">
<tbody><tr>
<th colspan="4">Inverse Bijective Transform</th>
</tr>
<tr>
<th colspan="4">Input</th>
</tr>
<tr>
<td colspan="4" align="center">
<pre>ANNBAA^
</pre></td>
</tr>
<tr>
<th>Add 1</th>
<th>Sort 1</th>
<th>Add 2</th>
<th>Sort 2</th>
</tr>
<tr>
<td align="right">
<pre>A
N
N
B
A
A
^
</pre></td>
<td align="right">
<pre>A
A
A
B
N
N
^
</pre></td>
<td align="right">
<pre>AA
NA
NA
BB
AN
AN
^^
</pre></td>
<td align="right">
<pre>AA
AN
AN
BB
NA
NA
^^
</pre></td>
</tr>
<tr>
<th>Add 3</th>
<th>Sort 3</th>
<th>Add 4</th>
<th>Sort 4</th>
</tr>
<tr>
<td align="right">
<pre>AAA
NAN
NAN
BBB
ANA
ANA
^^^
</pre></td>
<td align="right">
<pre>AAA
ANA
ANA
BBB
NAN
NAN
^^^
</pre></td>
<td align="right">
<pre>AAAA
NANA
NANA
BBBB
ANAN
ANAN
^^^^
</pre></td>
<td align="right">
<pre>AAAA
ANAN
ANAN
BBBB
NANA
NANA
^^^^
</pre></td>
</tr>
<tr>
<th colspan="4">Output</th>
</tr>
<tr>
<td colspan="4" align="center">
<pre>^BANANA
</pre></td>
</tr>
</tbody></table>
<p>Notice to get the above you can either view it as 4 cycles<br>
^ = (^)(^)... = ^^^^^...<br>
B = (B)(B)... = BBBB...<br>
ANAN = (ANAN)(ANAN)... = ANANANAN...<br>
A = (A)(A).. = AAAAA..<br>
or 5 cycles WHERE ANAN broken into 2<br>
AN = (AN) (AN) ... = ANANANAN<br>
AN = (AN) (AN) ... = ANANANAN</p>
<p>if a cycle is N character it will be repeated N times take lowest 
valve of each cycle then sort so highest first so in this case you get 
either<br>
(^)<br>
(B)<br>
(ANAN)<br>
(A)</p>
<p>or</p>
<p>(^)<br>
(B)<br>
(AN)<br>
(AN)<br>
(A)</p>
<p>to get the ^BANANA</p>
<p>Since any rotation of the input string will lead to the same 
transformed string, the BWT cannot be inverted without adding an 'EOF' 
marker to the input or, augmenting the output with information, such as 
an index, that makes it possible to identify the input string from the 
class of all of its rotations.</p>
<p>There is a <a href="http://en.wikipedia.org/wiki/Bijective" title="Bijective" class="mw-redirect">bijective</a>
 version of the transform, by which the transformed string uniquely 
identifies the original. In this version, every string has a unique 
inverse of the same length.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span>[</span>2<span>]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span>[</span>3<span>]</span></a></sup></p>
<p>If you check the internet of BWTS you will fine the code to do this 
bijective BWT. The fastest versions have been created by Yuta Mori and 
are linear in time and space. The first known version where coded by 
David A. Scott</p>
<p>The bijective transform is computed by first factoring the input into a non-increasing sequence of <a href="http://en.wikipedia.org/wiki/Lyndon_word" title="Lyndon word">Lyndon words</a>; such a factorization exists by the <a href="http://en.wikipedia.org/wiki/Chen%E2%80%93Fox%E2%80%93Lyndon_theorem" title="Chen–Fox–Lyndon theorem" class="mw-redirect">Chen–Fox–Lyndon theorem</a>,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span>[</span>4<span>]</span></a></sup> and can be found in linear time.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span>[</span>5<span>]</span></a></sup>
 Then, the algorithm sorts together all the rotations of all of these 
words; as in the usual Burrows–Wheeler transform, this produces a sorted
 sequence of <i>n</i> strings. The transformed string is then obtained by picking the final character of each of these strings in this sorted list.</p>
<p>For example, applying the bijective transform gives:</p>
<table class="wikitable">
<tbody><tr>
<th>Input</th>
<td><tt>SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES</tt></td>
</tr>
<tr>
<th>Lyndon words</th>
<td><tt><span style="color:#990000;">S</span><span style="color:#FF9900;">IX</span><span style="color:#006600;">.MIXED.PIXIES.SIFT.SIXTY.PIXIE</span><span style="color:#0000DD;">.DUST</span><span style="color:#660066;">.BOXES</span></tt></td>
</tr>
<tr>
<th>Output</th>
<td><tt>STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT</tt></td>
</tr>
</tbody></table>
<p>The bijective transform includes eight runs of identical characters. These runs are, in order: <tt>XX</tt>, <tt>II</tt>, <tt>XX</tt>, <tt>PP</tt>, <tt>..</tt>, <tt>EE</tt>, <tt>..</tt>, and <tt>IIII</tt>. In total, 18 characters take part in these runs.</p>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=4" title="Edit section: Dynamic Burrows–Wheeler transform">edit</a>]</span> <span class="mw-headline" id="Dynamic_Burrows.E2.80.93Wheeler_transform">Dynamic Burrows–Wheeler transform</span></h2>
<p>Instead of reconstructing the Burrows–Wheeler transform of an edited text, Salson <i>et al.</i><sup id="cite_ref-Salson2009_6-0" class="reference"><a href="#cite_note-Salson2009-6"><span>[</span>6<span>]</span></a></sup>
 propose an algorithm that deduces the new Burrows–Wheeler transform 
from the original one, doing a limited number of local reorderings in 
the original Burrows–Wheeler transform.</p>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=5" title="Edit section: Sample implementation">edit</a>]</span> <span class="mw-headline" id="Sample_implementation">Sample implementation</span></h2>
<p>This <a href="http://en.wikipedia.org/wiki/Python_%28programming_language%29" title="Python (programming language)">Python</a>
 implementation sacrifices speed for simplicity: the program is short, 
but takes more than the linear time that would be desired in a practical
 implementation.</p>
<p>Using the <a href="http://en.wikipedia.org/wiki/Null_character" title="Null character">null character</a> as the end of file marker, and using <code>s[i:] + s[:i]</code> to construct the <i>i</i>th rotation of <code>s</code>, the forward transform takes the last character of each of the sorted rows:</p>
<div dir="ltr" class="mw-geshi mw-code mw-content-ltr">
<div class="python source-python">
<pre class="de1"><span class="kw1">def</span> bwt<span class="br0">(</span>s<span class="br0">)</span>:
    <span class="st0">"""Apply Burrows-Wheeler transform to input string."""</span>
    <span class="kw1">assert</span> <span class="st0">"<span class="es0">\0</span>"</span> <span class="kw1">not</span> <span class="kw1">in</span> s<span class="sy0">,</span> <span class="st0">"Input string cannot contain null character ('<span class="es0">\\</span>0')"</span>
    s +<span class="sy0">=</span> <span class="st0">"<span class="es0">\0</span>"</span>  <span class="co1"># Add end of file marker</span>
    table <span class="sy0">=</span> <span class="kw2">sorted</span><span class="br0">(</span>s<span class="br0">[</span>i:<span class="br0">]</span> + s<span class="br0">[</span>:i<span class="br0">]</span> <span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw2">range</span><span class="br0">(</span><span class="kw2">len</span><span class="br0">(</span>s<span class="br0">)</span><span class="br0">)</span><span class="br0">)</span>  <span class="co1"># Table of rotations of string</span>
    last_column <span class="sy0">=</span> <span class="br0">[</span>row<span class="br0">[</span>-<span class="nu0">1</span>:<span class="br0">]</span> <span class="kw1">for</span> row <span class="kw1">in</span> table<span class="br0">]</span>  <span class="co1"># Last characters of each row</span>
    <span class="kw1">return</span> <span class="st0">""</span>.<span class="me1">join</span><span class="br0">(</span>last_column<span class="br0">)</span>  <span class="co1"># Convert list of characters into string</span>
</pre></div>
</div>
<p>The inverse transform repeatedly inserts <code>r</code> as the left 
column of the table and sorts the table. After the whole table is built,
 it returns the row that ends with null, minus the null.</p>
<div dir="ltr" class="mw-geshi mw-code mw-content-ltr">
<div class="python source-python">
<pre class="de1"><span class="kw1">def</span> ibwt<span class="br0">(</span>r<span class="br0">)</span>:
    <span class="st0">"""Apply inverse Burrows-Wheeler transform."""</span>
    table <span class="sy0">=</span> <span class="br0">[</span><span class="st0">""</span><span class="br0">]</span> * <span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span>  <span class="co1"># Make empty table</span>
    <span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw2">range</span><span class="br0">(</span><span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span><span class="br0">)</span>:
        table <span class="sy0">=</span> <span class="kw2">sorted</span><span class="br0">(</span>r<span class="br0">[</span>i<span class="br0">]</span> + table<span class="br0">[</span>i<span class="br0">]</span> <span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw2">range</span><span class="br0">(</span><span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span><span class="br0">)</span><span class="br0">)</span>  <span class="co1"># Add a column of r</span>
    s <span class="sy0">=</span> <span class="br0">[</span>row <span class="kw1">for</span> row <span class="kw1">in</span> table <span class="kw1">if</span> row.<span class="me1">endswith</span><span class="br0">(</span><span class="st0">"<span class="es0">\0</span>"</span><span class="br0">)</span><span class="br0">]</span><span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span>  <span class="co1"># Find the correct row (ending in "\0")</span>
    <span class="kw1">return</span> s.<span class="me1">rstrip</span><span class="br0">(</span><span class="st0">"<span class="es0">\0</span>"</span><span class="br0">)</span>  <span class="co1"># Get rid of trailing null character</span>
</pre></div>
</div>
<p>Here is another, more efficient method for the inverse transform. 
Although more complex, it increases the speed greatly when decoding 
lengthy strings.</p>
<div dir="ltr" class="mw-geshi mw-code mw-content-ltr">
<div class="python source-python">
<pre class="de1"><span class="kw1">def</span> ibwt<span class="br0">(</span>r<span class="sy0">,</span> *args<span class="br0">)</span>:
        <span class="st0">"Inverse Burrows-Wheeler transform. args is the original index <span class="es0">\</span>
if it was not indicated by a null byte"</span>
 
        firstCol <span class="sy0">=</span> <span class="st0">""</span>.<span class="me1">join</span><span class="br0">(</span><span class="kw2">sorted</span><span class="br0">(</span>r<span class="br0">)</span><span class="br0">)</span>
        count <span class="sy0">=</span> <span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span>*<span class="nu0">256</span>
        byteStart <span class="sy0">=</span> <span class="br0">[</span>-<span class="nu0">1</span><span class="br0">]</span>*<span class="nu0">256</span>
        output <span class="sy0">=</span> <span class="br0">[</span><span class="st0">""</span><span class="br0">]</span> * <span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span>
        shortcut <span class="sy0">=</span> <span class="br0">[</span><span class="kw2">None</span><span class="br0">]</span>*<span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span>
        <span class="co1">#Generates shortcut lists</span>
        <span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw2">range</span><span class="br0">(</span><span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span><span class="br0">)</span>:
                shortcutIndex <span class="sy0">=</span> <span class="kw2">ord</span><span class="br0">(</span>r<span class="br0">[</span>i<span class="br0">]</span><span class="br0">)</span>
                shortcut<span class="br0">[</span>i<span class="br0">]</span> <span class="sy0">=</span> count<span class="br0">[</span>shortcutIndex<span class="br0">]</span>
                count<span class="br0">[</span>shortcutIndex<span class="br0">]</span> +<span class="sy0">=</span> <span class="nu0">1</span>
                shortcutIndex <span class="sy0">=</span> <span class="kw2">ord</span><span class="br0">(</span>firstCol<span class="br0">[</span>i<span class="br0">]</span><span class="br0">)</span>
                <span class="kw1">if</span> byteStart<span class="br0">[</span>shortcutIndex<span class="br0">]</span> <span class="sy0">==</span> -<span class="nu0">1</span>:
                        byteStart<span class="br0">[</span>shortcutIndex<span class="br0">]</span> <span class="sy0">=</span> i
 
        localIndex <span class="sy0">=</span> <span class="br0">(</span>r.<span class="me1">index</span><span class="br0">(</span><span class="st0">"<span class="es0">\x</span>00"</span><span class="br0">)</span> <span class="kw1">if</span> <span class="kw1">not</span> args <span class="kw1">else</span> args<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span><span class="br0">)</span>
        <span class="kw1">for</span> i <span class="kw1">in</span> <span class="kw2">range</span><span class="br0">(</span><span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span><span class="br0">)</span>:
                <span class="co1">#takes the next index indicated by the transformation vector</span>
                nextByte <span class="sy0">=</span> r<span class="br0">[</span>localIndex<span class="br0">]</span>
                output <span class="br0">[</span><span class="kw2">len</span><span class="br0">(</span>r<span class="br0">)</span>-i-<span class="nu0">1</span><span class="br0">]</span> <span class="sy0">=</span> nextByte
                shortcutIndex <span class="sy0">=</span> <span class="kw2">ord</span><span class="br0">(</span>nextByte<span class="br0">)</span>
                <span class="co1">#assigns localIndex to the next index in the transformation vector</span>
                localIndex <span class="sy0">=</span> byteStart<span class="br0">[</span>shortcutIndex<span class="br0">]</span> + shortcut<span class="br0">[</span>localIndex<span class="br0">]</span>
        <span class="kw1">return</span> <span class="st0">""</span>.<span class="me1">join</span><span class="br0">(</span>output<span class="br0">)</span>.<span class="me1">rstrip</span><span class="br0">(</span><span class="st0">"<span class="es0">\x</span>00"</span><span class="br0">)</span>
</pre></div>
</div>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=6" title="Edit section: BWT in bioinformatics">edit</a>]</span> <span class="mw-headline" id="BWT_in_bioinformatics">BWT in bioinformatics</span></h2>
<p>The advent of <a href="http://en.wikipedia.org/wiki/High-throughput_sequencing" title="High-throughput sequencing" class="mw-redirect">high-throughput sequencing</a> (HTS) techniques at the end of the 2000 decade has led to another application of the Burrows–Wheeler transformation. In HTS, <a href="http://en.wikipedia.org/wiki/DNA" title="DNA">DNA</a> is fragmented into small pieces, of which the first few bases are <a href="http://en.wikipedia.org/wiki/DNA_sequencing" title="DNA sequencing">sequenced</a>, yielding several millions of "reads", each 30 to 500 <a href="http://en.wikipedia.org/wiki/Base_pair" title="Base pair">base pairs</a> ("DNA characters") long. In many experiments, e.g., in <a href="http://en.wikipedia.org/wiki/ChIP-Seq" title="ChIP-Seq" class="mw-redirect">ChIP-Seq</a>, the task is now to align these reads to a reference <a href="http://en.wikipedia.org/wiki/Genome" title="Genome">genome</a>,
 i.e., to the known, nearly complete sequence of the organism in 
question (which may be up to several billion base pairs long). A number 
of alignment programs, specialized for this task, were published, which 
initially relied on <a href="http://en.wikipedia.org/wiki/Hashing" title="Hashing" class="mw-redirect">hashing</a> (e.g., <a href="http://en.wikipedia.org/w/index.php?title=Eland_%28software%29&amp;action=edit&amp;redlink=1" class="new" title="Eland (software) (page does not exist)">Eland</a>, <a rel="nofollow" class="external text" href="http://soap.genomics.org.cn/">SOAP</a>,<sup id="cite_ref-Li.2C_R2008_7-0" class="reference"><a href="#cite_note-Li.2C_R2008-7"><span>[</span>7<span>]</span></a></sup> or <a href="http://en.wikipedia.org/w/index.php?title=Maq&amp;action=edit&amp;redlink=1" class="new" title="Maq (page does not exist)">Maq</a><sup id="cite_ref-Li.2C_H2008_8-0" class="reference"><a href="#cite_note-Li.2C_H2008-8"><span>[</span>8<span>]</span></a></sup>). In an effort to reduce the memory requirement for sequence alignment, several alignment programs were developed (Bowtie,<sup id="cite_ref-Langmead2009_9-0" class="reference"><a href="#cite_note-Langmead2009-9"><span>[</span>9<span>]</span></a></sup> BWA,<sup id="cite_ref-Li.2C_H2009_10-0" class="reference"><a href="#cite_note-Li.2C_H2009-10"><span>[</span>10<span>]</span></a></sup> and SOAP2<sup id="cite_ref-Li.2C_R2009_11-0" class="reference"><a href="#cite_note-Li.2C_R2009-11"><span>[</span>11<span>]</span></a></sup>) which use the Burrows–Wheeler transform.</p>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=7" title="Edit section: References">edit</a>]</span> <span class="mw-headline" id="References">References</span></h2>
<div class="reflist references-column-count references-column-count-2" style="-moz-column-count: 2; -webkit-column-count: 2; column-count: 2; list-style-type: decimal;">
<ol class="references">
<li id="cite_note-Burrows1994-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-Burrows1994_1-0">^</a></b></span> <span class="reference-text"><span class="citation" id="CITEREFBurrows_M_and_Wheeler_D1994">Burrows M and Wheeler D (1994), <a rel="nofollow" class="external text" href="http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html"><i>A block sorting lossless data compression algorithm</i></a>, Technical Report 124, Digital Equipment Corporation<span class="printonly">, <a rel="nofollow" class="external free" href="http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html">http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html</a></span></span></span></li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><span class="citation" id="CITEREFGilScott2009">Gil, J.; Scott, D. A. (2009), <a rel="nofollow" class="external text" href="http://bijective.dogma.net/00yyy.pdf"><i>A bijective string sorting transform</i></a><span class="printonly">, <a rel="nofollow" class="external free" href="http://bijective.dogma.net/00yyy.pdf">http://bijective.dogma.net/00yyy.pdf</a></span></span></span></li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><span class="citation" id="CITEREFKufleitner2009">Kufleitner, Manfred (2009), <a rel="nofollow" class="external text" href="http://www.stringology.org/event/2009/p07.html">"On bijective variants of the Burrows-Wheeler transform"</a>, in Holub, Jan; Žďárek, Jan, <i>Prague Stringology Conference</i>, pp.&nbsp;65–69, <a href="http://en.wikipedia.org/wiki/ArXiv" title="ArXiv">arXiv</a>:<a rel="nofollow" class="external text" href="http://arxiv.org/abs/0908.0239">0908.0239</a><span class="printonly">, <a rel="nofollow" class="external free" href="http://www.stringology.org/event/2009/p07.html">http://www.stringology.org/event/2009/p07.html</a></span></span>.</span></li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">*<span class="citation" id="CITEREFLothaire1997"><a href="http://en.wikipedia.org/wiki/M._Lothaire" title="M. Lothaire">Lothaire, M.</a> (1997), <i>Combinatorics on words</i>, Encyclopedia of Mathematics and Its Applications, <b>17</b>,
 Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; 
Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, 
C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon 
(2nd ed.), <a href="http://en.wikipedia.org/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, p.&nbsp;67, <a href="http://en.wikipedia.org/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a>&nbsp;<a href="http://en.wikipedia.org/wiki/Special:BookSources/0-521-59924-5" title="Special:BookSources/0-521-59924-5">0-521-59924-5</a>, <a href="http://en.wikipedia.org/wiki/Zentralblatt_MATH" title="Zentralblatt MATH">Zbl</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.zentralblatt-math.org/zmath/en/search/?q=an:0874.20040&amp;format=complete">0874.20040</a></span></span></li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><span class="citation" id="CITEREFDuval1983_zbl.3D0532.68061">Duval, Jean-Pierre (1983 zbl=0532.68061), "Factorizing words over an ordered alphabet", <i>Journal of Algorithms</i> <b>4</b> (4): 363–381, <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1016%2F0196-6774%2883%2990017-2">10.1016/0196-6774(83)90017-2</a>, <a href="http://en.wikipedia.org/wiki/International_Standard_Serial_Number" title="International Standard Serial Number">ISSN</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.worldcat.org/issn/0196-6774">0196-6774</a></span>.</span></li>
<li id="cite_note-Salson2009-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Salson2009_6-0">^</a></b></span> <span class="reference-text"><span class="citation Journal">Salson M, Lecroq T, Léonard M and Mouchard L (2009). "A Four-Stage Algorithm for Updating a Burrows–Wheeler Transform". <i>Theoretical Computer Science</i> <b>410</b> (43): 4350. <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1016%2Fj.tcs.2009.07.016">10.1016/j.tcs.2009.07.016</a>.</span></span></li>
<li id="cite_note-Li.2C_R2008-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-Li.2C_R2008_7-0">^</a></b></span> <span class="reference-text"><span class="citation Journal">Li R, <i>et al.</i> (2008). "SOAP: short oligonucleotide alignment program". <i>Bioinformatics</i> <b>24</b> (5): 713–714. <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1093%2Fbioinformatics%2Fbtn025">10.1093/bioinformatics/btn025</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Identifier" title="PubMed Identifier" class="mw-redirect">PMID</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pubmed/18227114">18227114</a>.</span></span></li>
<li id="cite_note-Li.2C_H2008-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Li.2C_H2008_8-0">^</a></b></span> <span class="reference-text"><span class="citation Journal">Li H, Ruan J, Durbin R (2008-08-19). <a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2577856/">"Mapping short DNA sequencing reads and calling variants using mapping quality scores"</a>. <i>Genome Research</i> <b>18</b> (11): 1851–1858. <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1101%2Fgr.078212.108">10.1101/gr.078212.108</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Central" title="PubMed Central">PMC</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2577856">2577856</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Identifier" title="PubMed Identifier" class="mw-redirect">PMID</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pubmed/18714091">18714091</a><span class="printonly">. //www.ncbi.nlm.nih.gov/pmc/articles/PMC2577856/</span>.</span></span></li>
<li id="cite_note-Langmead2009-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-Langmead2009_9-0">^</a></b></span> <span class="reference-text"><span class="citation Journal">Langmead B, Trapnell C, Pop M, Salzberg SL (2009). <a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2690996/">"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome"</a>. <i>Genome Biology</i> <b>10</b> (3): R25. <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1186%2Fgb-2009-10-3-r25">10.1186/gb-2009-10-3-r25</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Central" title="PubMed Central">PMC</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2690996">2690996</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Identifier" title="PubMed Identifier" class="mw-redirect">PMID</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pubmed/19261174">19261174</a><span class="printonly">. //www.ncbi.nlm.nih.gov/pmc/articles/PMC2690996/</span>.</span></span></li>
<li id="cite_note-Li.2C_H2009-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-Li.2C_H2009_10-0">^</a></b></span> <span class="reference-text"><span class="citation Journal">Li H, Durbin R (2009). <a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2705234/">"Fast and accurate short read alignment with Burrows–Wheeler Transform"</a>. <i>Bioinformatics</i> <b>25</b> (14): 1754–1760. <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1093%2Fbioinformatics%2Fbtp324">10.1093/bioinformatics/btp324</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Central" title="PubMed Central">PMC</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2705234">2705234</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Identifier" title="PubMed Identifier" class="mw-redirect">PMID</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pubmed/19451168">19451168</a><span class="printonly">. //www.ncbi.nlm.nih.gov/pmc/articles/PMC2705234/</span>.</span></span></li>
<li id="cite_note-Li.2C_R2009-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-Li.2C_R2009_11-0">^</a></b></span> <span class="reference-text"><span class="citation Journal">Li R, <i>et al.</i> (2009). "SOAP2: an improved ultrafast tool for short read alignment". <i>Bioinformatics</i> <b>25</b> (15): 1966–1967. <a href="http://en.wikipedia.org/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="http://dx.doi.org/10.1093%2Fbioinformatics%2Fbtp336">10.1093/bioinformatics/btp336</a>. <a href="http://en.wikipedia.org/wiki/PubMed_Identifier" title="PubMed Identifier" class="mw-redirect">PMID</a>&nbsp;<a rel="nofollow" class="external text" href="http://www.ncbi.nlm.nih.gov/pubmed/19497933">19497933</a>.</span></span></li>
</ol>
</div>
<h2><span class="editsection">[<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit&amp;section=8" title="Edit section: External links">edit</a>]</span> <span class="mw-headline" id="External_links">External links</span></h2>
<ul>
<li><a rel="nofollow" class="external text" href="http://compressionratings.com/bwt.html">Compression comparison of BWT based file compressors</a></li>
<li><a rel="nofollow" class="external text" href="http://marknelson.us/1996/09/01/bwt/">Article by Mark Nelson on the BWT</a></li>
<li><a rel="nofollow" class="external text" href="http://bijective.dogma.net/00yyy.pdf">A Bijective String-Sorting Transform, by Gil and Scott</a></li>
<li><a rel="nofollow" class="external text" href="http://encode.ru/attachment.php?attachmentid=959&amp;d=1249146089">Yuta's openbwt-v1.5.zip contains source code for various BWT routines including BWTS for bijective version</a></li>
<li><a rel="nofollow" class="external text" href="http://arxiv.org/abs/0908.0239">On Bijective Variants of the Burrows–Wheeler Transform, by Kufleitner</a></li>
<li><a rel="nofollow" class="external text" href="http://google-opensource.blogspot.com/2008/06/debuting-dcs-bwt-experimental-burrows.html">Blog post</a> and <a rel="nofollow" class="external text" href="http://code.google.com/p/dcs-bwt-compressor/">project page</a> for an open-source compression program and library based on the Burrows–Wheeler algorithm</li>
</ul>
<table class="navbox" style="border-spacing:0;;" cellspacing="0">
<tbody><tr>
<td style="padding:2px;">
<table id="collapsibleTable0" class="nowraplinks collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit;;" cellspacing="0">
<tbody><tr>
<th scope="col" style=";" class="navbox-title" colspan="2"><span class="collapseButton">[<a href="#" id="collapseButton0">hide</a>]</span>
<div class="noprint plainlinks hlist navbar mini" style="">
<ul>
<li class="nv-view"><a href="http://en.wikipedia.org/wiki/Template:Compression_methods" title="Template:Compression methods"><span title="View this template" style=";;background:none transparent;border:none;">v</span></a></li>
<li class="nv-talk"><a href="http://en.wikipedia.org/wiki/Template_talk:Compression_methods" title="Template talk:Compression methods"><span title="Discuss this template" style=";;background:none transparent;border:none;">t</span></a></li>
<li class="nv-edit"><a class="external text" href="http://en.wikipedia.org/w/index.php?title=Template:Compression_methods&amp;action=edit"><span title="Edit this template" style=";;background:none transparent;border:none;">e</span></a></li>
</ul>
</div>
<div class="" style="font-size:110%;"><a href="http://en.wikipedia.org/wiki/Data_compression" title="Data compression">Data compression</a> methods</div>
</th>
</tr>
<tr style="height:2px;">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";;"><a href="http://en.wikipedia.org/wiki/Information_theory" title="Information theory">Information theory</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-odd hlist">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Entropy_%28information_theory%29" title="Entropy (information theory)">Entropy</a></li>
<li><a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" title="Kolmogorov complexity">Complexity</a></li>
<li><a href="http://en.wikipedia.org/wiki/Redundancy_%28information_theory%29" title="Redundancy (information theory)">Redundancy</a></li>
<li><a href="http://en.wikipedia.org/wiki/Lossy_compression" title="Lossy compression">Lossy</a></li>
<li><a href="http://en.wikipedia.org/wiki/Timeline_of_information_theory" title="Timeline of information theory">Timeline of information theory</a></li>
<li><a href="http://en.wikipedia.org/wiki/Quantization_%28signal_processing%29" title="Quantization (signal processing)">Quantization</a></li>
<li><a href="http://en.wikipedia.org/wiki/Rate_distortion_theory" title="Rate distortion theory" class="mw-redirect">Rate distortion theory</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";;"><a href="http://en.wikipedia.org/wiki/Lossless_data_compression" title="Lossless data compression" class="mw-redirect">Lossless</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-even hlist">
<div style="padding:0em 0.25em"></div>
<table class="nowraplinks navbox-subgroup" style="border-spacing:0;;;;" cellspacing="0">
<tbody><tr>
<th scope="row" class="navbox-group" style=";width:11em;;"><a href="http://en.wikipedia.org/wiki/Entropy_encoding" title="Entropy encoding">Entropy encoding</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano</a></li>
<li><a href="http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano%E2%80%93Elias_coding" title="Shannon–Fano–Elias coding">Shannon–Fano–Elias</a></li>
<li><a href="http://en.wikipedia.org/wiki/Huffman_coding" title="Huffman coding">Huffman</a>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Adaptive_Huffman_coding" title="Adaptive Huffman coding">Adaptive</a></li>
<li><a href="http://en.wikipedia.org/wiki/Canonical_Huffman_code" title="Canonical Huffman code">Canonical</a></li>
<li><a href="http://en.wikipedia.org/wiki/Modified_Huffman_coding" title="Modified Huffman coding">Modified</a></li>
</ul>
</li>
<li><a href="http://en.wikipedia.org/wiki/Arithmetic_coding" title="Arithmetic coding">Arithmetic</a></li>
<li><a href="http://en.wikipedia.org/wiki/Range_encoding" title="Range encoding">Range</a></li>
<li><a href="http://en.wikipedia.org/wiki/Golomb_coding" title="Golomb coding">Golomb</a></li>
<li><a href="http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29" title="Universal code (data compression)">Universal</a>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Elias_gamma_coding" title="Elias gamma coding">Gamma</a></li>
<li><a href="http://en.wikipedia.org/wiki/Exponential-Golomb_coding" title="Exponential-Golomb coding">Exp-Golomb</a></li>
<li><a href="http://en.wikipedia.org/wiki/Fibonacci_coding" title="Fibonacci coding">Fibonacci</a></li>
<li><a href="http://en.wikipedia.org/wiki/Levenstein_coding" title="Levenstein coding">Levenstein</a></li>
</ul>
</li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;"><a href="http://en.wikipedia.org/wiki/Dictionary_coder" title="Dictionary coder">Dictionary</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-even">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Run-length_encoding" title="Run-length encoding">RLE</a></li>
<li><a href="http://en.wikipedia.org/wiki/Byte_pair_encoding" title="Byte pair encoding">Byte pair encoding</a></li>
<li><a href="http://en.wikipedia.org/wiki/DEFLATE" title="DEFLATE">DEFLATE</a></li>
<li>Lempel–Ziv
<ul>
<li><a href="http://en.wikipedia.org/wiki/LZ77_and_LZ78" title="LZ77 and LZ78">LZ77 and LZ78</a></li>
<li><a href="http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski" title="Lempel–Ziv–Storer–Szymanski">LZSS</a></li>
<li><a href="http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch" title="Lempel–Ziv–Welch">LZW</a></li>
<li><a href="http://en.wikipedia.org/wiki/LZWL" title="LZWL">LZWL</a></li>
<li><a href="http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Oberhumer" title="Lempel–Ziv–Oberhumer">LZO</a></li>
<li><a href="http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm" title="Lempel–Ziv–Markov chain algorithm">LZMA</a></li>
<li><a href="http://en.wikipedia.org/wiki/LZX_%28algorithm%29" title="LZX (algorithm)">LZX</a></li>
<li><a href="http://en.wikipedia.org/wiki/LZRW" title="LZRW">LZRW</a></li>
<li><a href="http://en.wikipedia.org/wiki/LZJB" title="LZJB">LZJB</a></li>
<li><a href="http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Stac" title="Lempel–Ziv–Stac">LZS</a></li>
<li><a href="http://en.wikipedia.org/w/index.php?title=Lempel%E2%80%93Ziv%E2%80%93Tamayo&amp;action=edit&amp;redlink=1" class="new" title="Lempel–Ziv–Tamayo (page does not exist)">LZT</a></li>
<li><a href="http://en.wikipedia.org/w/index.php?title=Reduced_Offset_Lempel_Ziv&amp;action=edit&amp;redlink=1" class="new" title="Reduced Offset Lempel Ziv (page does not exist)">ROLZ</a></li>
<li><a href="http://en.wikipedia.org/wiki/Statistical_Lempel_Ziv" title="Statistical Lempel Ziv">Statistical Lempel Ziv</a></li>
</ul>
</li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Others</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Context_tree_weighting" title="Context tree weighting">CTW</a></li>
<li><strong class="selflink">BWT</strong></li>
<li><a href="http://en.wikipedia.org/wiki/Prediction_by_partial_matching" title="Prediction by partial matching">PPM</a></li>
<li><a href="http://en.wikipedia.org/wiki/Dynamic_Markov_compression" title="Dynamic Markov compression">DMC</a></li>
<li><a href="http://en.wikipedia.org/wiki/Delta_encoding" title="Delta encoding">Delta</a></li>
</ul>
</div>
</td>
</tr>
</tbody></table>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";;"><a href="http://en.wikipedia.org/wiki/Audio_compression_%28data%29" title="Audio compression (data)" class="mw-redirect">Audio</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-odd hlist">
<div style="padding:0em 0.25em"></div>
<table class="nowraplinks navbox-subgroup" style="border-spacing:0;;;;" cellspacing="0">
<tbody><tr>
<th scope="row" class="navbox-group" style=";width:11em;;"><a href="http://en.wikipedia.org/wiki/Acoustics" title="Acoustics">Theory</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Companding" title="Companding">Companding</a></li>
<li><a href="http://en.wikipedia.org/wiki/Convolution" title="Convolution">Convolution</a></li>
<li><a href="http://en.wikipedia.org/wiki/Dynamic_range" title="Dynamic range">Dynamic range</a></li>
<li><a href="http://en.wikipedia.org/wiki/Latency_%28audio%29" title="Latency (audio)">Latency</a></li>
<li><a href="http://en.wikipedia.org/wiki/Sampling_%28signal_processing%29" title="Sampling (signal processing)">Sampling</a></li>
<li><a href="http://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon theorem</a></li>
<li><a href="http://en.wikipedia.org/wiki/Sound_quality" title="Sound quality">Sound quality</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;"><a href="http://en.wikipedia.org/wiki/Audio_codec" title="Audio codec">Audio codec</a> parts</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-even">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Linear_predictive_coding" title="Linear predictive coding">LPC</a>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Log_area_ratio" title="Log area ratio">LAR</a></li>
<li><a href="http://en.wikipedia.org/wiki/Line_spectral_pairs" title="Line spectral pairs">LSP</a></li>
</ul>
</li>
<li><a href="http://en.wikipedia.org/wiki/Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li>
<li><a href="http://en.wikipedia.org/wiki/Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li>
<li><a href="http://en.wikipedia.org/wiki/Algebraic_Code_Excited_Linear_Prediction" title="Algebraic Code Excited Linear Prediction" class="mw-redirect">ACELP</a></li>
<li><a href="http://en.wikipedia.org/wiki/A-law_algorithm" title="A-law algorithm">A-law</a></li>
<li><a href="http://en.wikipedia.org/wiki/%CE%9C-law_algorithm" title="Μ-law algorithm">μ-law</a></li>
<li><a href="http://en.wikipedia.org/wiki/Adaptive_DPCM" title="Adaptive DPCM" class="mw-redirect">ADPCM</a></li>
<li><a href="http://en.wikipedia.org/wiki/DPCM" title="DPCM" class="mw-redirect">DPCM</a></li>
<li><a href="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li>
<li><a href="http://en.wikipedia.org/wiki/Fourier_transform" title="Fourier transform">Fourier transform</a></li>
<li><a href="http://en.wikipedia.org/wiki/Psychoacoustics" title="Psychoacoustics">Psychoacoustic model</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Others</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Bit_rate" title="Bit rate">Bit rate</a>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Constant_bitrate" title="Constant bitrate">CBR</a></li>
<li><a href="http://en.wikipedia.org/wiki/Average_bitrate" title="Average bitrate">ABR</a></li>
<li><a href="http://en.wikipedia.org/wiki/Variable_bitrate" title="Variable bitrate">VBR</a></li>
</ul>
</li>
<li><a href="http://en.wikipedia.org/wiki/Speech_encoding" title="Speech encoding" class="mw-redirect">Speech compression</a></li>
<li><a href="http://en.wikipedia.org/wiki/Sub-band_coding" title="Sub-band coding">Sub-band coding</a></li>
</ul>
</div>
</td>
</tr>
</tbody></table>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";;"><a href="http://en.wikipedia.org/wiki/Image_compression" title="Image compression">Image</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-even hlist">
<div style="padding:0em 0.25em"></div>
<table class="nowraplinks navbox-subgroup" style="border-spacing:0;;;;" cellspacing="0">
<tbody><tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Terms</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Color_space" title="Color space">Color space</a></li>
<li><a href="http://en.wikipedia.org/wiki/Pixel" title="Pixel">Pixel</a></li>
<li><a href="http://en.wikipedia.org/wiki/Chroma_subsampling" title="Chroma subsampling">Chroma subsampling</a></li>
<li><a href="http://en.wikipedia.org/wiki/Compression_artifact" title="Compression artifact">Compression artifact</a></li>
<li><a href="http://en.wikipedia.org/wiki/Image_resolution" title="Image resolution">Image resolution</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Methods</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-even">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Run-length_encoding" title="Run-length encoding">RLE</a></li>
<li><a href="http://en.wikipedia.org/wiki/Fractal_compression" title="Fractal compression">Fractal</a></li>
<li><a href="http://en.wikipedia.org/wiki/Wavelet_compression" title="Wavelet compression" class="mw-redirect">Wavelet</a></li>
<li><a href="http://en.wikipedia.org/wiki/EZW" title="EZW" class="mw-redirect">EZW</a></li>
<li><a href="http://en.wikipedia.org/wiki/Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li>
<li><a href="http://en.wikipedia.org/wiki/Pyramid_%28image_processing%29" title="Pyramid (image processing)">LP</a></li>
<li><a href="http://en.wikipedia.org/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li>
<li><a href="http://en.wikipedia.org/wiki/Chain_code" title="Chain code">Chain code</a></li>
<li><a href="http://en.wikipedia.org/wiki/Karhunen-Lo%C3%A8ve_transform" title="Karhunen-Loève transform" class="mw-redirect">KLT</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Others</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Standard_test_image" title="Standard test image">Test images</a></li>
<li><a href="http://en.wikipedia.org/wiki/Peak_signal-to-noise_ratio" title="Peak signal-to-noise ratio">PSNR quality measure</a></li>
<li><a href="http://en.wikipedia.org/wiki/Quantization_%28image_processing%29" title="Quantization (image processing)">Quantization</a></li>
</ul>
</div>
</td>
</tr>
</tbody></table>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";;"><a href="http://en.wikipedia.org/wiki/Video_compression" title="Video compression" class="mw-redirect">Video</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-odd hlist">
<div style="padding:0em 0.25em"></div>
<table class="nowraplinks navbox-subgroup" style="border-spacing:0;;;;" cellspacing="0">
<tbody><tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Terms</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Video#Characteristics_of_video_streams" title="Video">Video characteristics</a></li>
<li><a href="http://en.wikipedia.org/wiki/Film_frame" title="Film frame">Frame</a></li>
<li><a href="http://en.wikipedia.org/wiki/Frame_rate" title="Frame rate">Frame rate</a></li>
<li><a href="http://en.wikipedia.org/wiki/Interlaced_video" title="Interlaced video">Interlace</a></li>
<li><a href="http://en.wikipedia.org/wiki/Video_compression_picture_types" title="Video compression picture types">Frame types</a></li>
<li><a href="http://en.wikipedia.org/wiki/Video_quality" title="Video quality">Video quality</a></li>
<li><a href="http://en.wikipedia.org/wiki/Video_resolution" title="Video resolution" class="mw-redirect">Video resolution</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;"><a href="http://en.wikipedia.org/wiki/Video_codec" title="Video codec">Video codec parts</a></th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-even">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Motion_compensation" title="Motion compensation">Motion compensation</a></li>
<li><a href="http://en.wikipedia.org/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li>
</ul>
</div>
</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<th scope="row" class="navbox-group" style=";width:11em;;">Others</th>
<td style="text-align:left;border-left-width:2px;border-left-style:solid;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em">
<ul>
<li><a href="http://en.wikipedia.org/wiki/Video_codec" title="Video codec">Video codecs</a></li>
<li><a href="http://en.wikipedia.org/wiki/List_of_codecs#Lossless_compression" title="List of codecs">Lossless compressed</a></li>
<li><a href="http://en.wikipedia.org/wiki/Uncompressed_video" title="Uncompressed video">Uncompressed</a></li>
<li><a href="http://en.wikipedia.org/wiki/Bit_rate" title="Bit rate">Bit rate</a>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Constant_bitrate" title="Constant bitrate">CBR</a></li>
<li><a href="http://en.wikipedia.org/wiki/Average_bitrate" title="Average bitrate">ABR</a></li>
<li><a href="http://en.wikipedia.org/wiki/Variable_bitrate" title="Variable bitrate">VBR</a></li>
</ul>
</li>
</ul>
</div>
</td>
</tr>
</tbody></table>
</td>
</tr>
<tr style="height:2px;">
<td></td>
</tr>
<tr>
<td class="navbox-abovebelow" style=";" colspan="2">
<div>See <a href="http://en.wikipedia.org/wiki/Template:Compression_formats" title="Template:Compression formats">Compression formats</a> for formats and <a href="http://en.wikipedia.org/wiki/Template:Compression_software" title="Template:Compression software">Compression software</a> for codecs</div>
</td>
</tr>
</tbody></table>
</td>
</tr>
</tbody></table>


<!-- 
NewPP limit report
Preprocessor visited node count: 9503/1000000
Preprocessor generated node count: 32828/1500000
Post-expand include size: 100920/2048000 bytes
Template argument size: 48426/2048000 bytes
Highest expansion depth: 21/40
Expensive parser function count: 2/500
-->

<!-- Saved in parser cache with key enwiki:pcache:idhash:36777-0!*!0!!en!4!* and timestamp 20130113181038 -->
</div>				<!-- /bodycontent -->
								<!-- printfooter -->
				<div class="printfooter">
				Retrieved from "<a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;oldid=526993356">http://en.wikipedia.org/w/index.php?title=Burrows–Wheeler_transform&amp;oldid=526993356</a>"				</div>
				<!-- /printfooter -->
												<!-- catlinks -->
				<div class="articleFeedback" id="mw-articlefeedback"><div class="articleFeedback-panel">	<div class="articleFeedback-buffer articleFeedback-ui">		<div class="articleFeedback-switch articleFeedback-switch-report articleFeedback-visibleWith-form" rel="report">View page ratings</div>		<div style="display: none;" class="articleFeedback-switch articleFeedback-switch-form articleFeedback-visibleWith-report" rel="form">Rate this page</div>		<div class="articleFeedback-title articleFeedback-visibleWith-form">Rate this page</div>		<div style="display: none;" class="articleFeedback-title articleFeedback-visibleWith-report">Page ratings</div>		<div class="articleFeedback-explanation articleFeedback-visibleWith-form"><a href="http://en.wikipedia.org/wiki/Wikipedia:Article%20Feedback%20Tool" class="articleFeedback-explanation-link">What's this?</a></div>		<div style="display: none;" class="articleFeedback-description articleFeedback-visibleWith-report">Current average ratings.</div>		<div style="clear:both;"></div>		<div class="articleFeedback-ratings"><div rel="trustworthy" class="articleFeedback-rating">	<div original-title="Do you feel this page has sufficient citations and that those citations come from trustworthy sources?" class="articleFeedback-label">Trustworthy</div>	<input name="r1" type="hidden">	<div class="articleFeedback-rating-labels articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-label" rel="1"></div>		<div class="articleFeedback-rating-label" rel="2"></div>		<div class="articleFeedback-rating-label" rel="3"></div>		<div class="articleFeedback-rating-label" rel="4"></div>		<div class="articleFeedback-rating-label" rel="5"></div>		<div original-title="Remove this rating" class="articleFeedback-rating-clear"></div>	</div>	<div class="articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-tooltip"></div>	</div>	<div style="display: none;" class="articleFeedback-rating-average articleFeedback-visibleWith-report"></div>	<div style="display: none;" class="articleFeedback-rating-meter articleFeedback-visibleWith-report"><div></div></div>	<div style="display: none;" class="articleFeedback-rating-count articleFeedback-visibleWith-report"></div>	<div style="clear:both;"></div></div><div rel="objective" class="articleFeedback-rating">	<div original-title="Do you feel that this page shows a fair representation of all perspectives on the issue?" class="articleFeedback-label">Objective</div>	<input name="r2" type="hidden">	<div class="articleFeedback-rating-labels articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-label" rel="1"></div>		<div class="articleFeedback-rating-label" rel="2"></div>		<div class="articleFeedback-rating-label" rel="3"></div>		<div class="articleFeedback-rating-label" rel="4"></div>		<div class="articleFeedback-rating-label" rel="5"></div>		<div original-title="Remove this rating" class="articleFeedback-rating-clear"></div>	</div>	<div class="articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-tooltip"></div>	</div>	<div style="display: none;" class="articleFeedback-rating-average articleFeedback-visibleWith-report"></div>	<div style="display: none;" class="articleFeedback-rating-meter articleFeedback-visibleWith-report"><div></div></div>	<div style="display: none;" class="articleFeedback-rating-count articleFeedback-visibleWith-report"></div>	<div style="clear:both;"></div></div><div rel="complete" class="articleFeedback-rating">	<div original-title="Do you feel that this page covers the essential topic areas that it should?" class="articleFeedback-label">Complete</div>	<input name="r3" type="hidden">	<div class="articleFeedback-rating-labels articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-label" rel="1"></div>		<div class="articleFeedback-rating-label" rel="2"></div>		<div class="articleFeedback-rating-label" rel="3"></div>		<div class="articleFeedback-rating-label" rel="4"></div>		<div class="articleFeedback-rating-label" rel="5"></div>		<div original-title="Remove this rating" class="articleFeedback-rating-clear"></div>	</div>	<div class="articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-tooltip"></div>	</div>	<div style="display: none;" class="articleFeedback-rating-average articleFeedback-visibleWith-report"></div>	<div style="display: none;" class="articleFeedback-rating-meter articleFeedback-visibleWith-report"><div></div></div>	<div style="display: none;" class="articleFeedback-rating-count articleFeedback-visibleWith-report"></div>	<div style="clear:both;"></div></div><div rel="wellwritten" class="articleFeedback-rating">	<div original-title="Do you feel that this page is well-organized and well-written?" class="articleFeedback-label">Well-written</div>	<input name="r4" type="hidden">	<div class="articleFeedback-rating-labels articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-label" rel="1"></div>		<div class="articleFeedback-rating-label" rel="2"></div>		<div class="articleFeedback-rating-label" rel="3"></div>		<div class="articleFeedback-rating-label" rel="4"></div>		<div class="articleFeedback-rating-label" rel="5"></div>		<div original-title="Remove this rating" class="articleFeedback-rating-clear"></div>	</div>	<div class="articleFeedback-visibleWith-form">		<div class="articleFeedback-rating-tooltip"></div>	</div>	<div style="display: none;" class="articleFeedback-rating-average articleFeedback-visibleWith-report"></div>	<div style="display: none;" class="articleFeedback-rating-meter articleFeedback-visibleWith-report"><div></div></div>	<div style="display: none;" class="articleFeedback-rating-count articleFeedback-visibleWith-report"></div>	<div style="clear:both;"></div></div></div>		<div style="clear:both;"></div>		<div class="articleFeedback-options">			<div class="articleFeedback-expertise articleFeedback-visibleWith-form">				<input id="articleFeedback-expertise-general" value="general" disabled="disabled" type="checkbox"><label for="articleFeedback-expertise-general" class="articleFeedback-expertise-disabled">I am highly knowledgeable about this topic (optional)</label>				<div class="articleFeedback-expertise-options">					<div><input id="articleFeedback-expertise-studies" value="studies" type="checkbox"><label for="articleFeedback-expertise-studies">I have a relevant college/university degree</label></div>					<div><input id="articleFeedback-expertise-profession" value="profession" type="checkbox"><label for="articleFeedback-expertise-profession">It is part of my profession</label></div>					<div><input id="articleFeedback-expertise-hobby" value="hobby" type="checkbox"><label for="articleFeedback-expertise-hobby">It is a deep personal passion</label></div>					<div><input id="articleFeedback-expertise-other" value="other" type="checkbox"><label for="articleFeedback-expertise-other">The source of my knowledge is not listed here</label></div>					<div class="articleFeedback-helpimprove">						<input id="articleFeedback-expertise-helpimprove-email" value="helpimprove-email" type="checkbox">						<label for="articleFeedback-expertise-helpimprove-email">I would like to help improve Wikipedia, send me an e-mail (optional)</label>						<input placeholder="email@example.org" class="articleFeedback-helpimprove-email" type="text">						<div class="articleFeedback-helpimprove-note">We will send you a confirmation e-mail. We will not share your e-mail address with outside parties as per our <a href="http://wikimediafoundation.org/wiki/Feedback_privacy_statement">feedback privacy statement</a>.</div>					</div>				</div>			</div>			<div style="clear:both;"></div>		</div>		<button aria-disabled="true" role="button" class="articleFeedback-submit articleFeedback-visibleWith-form ui-button ui-widget ui-state-default ui-corner-all ui-button-disabled ui-state-disabled ui-button-text-only ui-button-blue" type="submit" disabled="disabled"><span class="ui-button-text">Submit ratings</span></button>		<div class="articleFeedback-success articleFeedback-visibleWith-form"><span>Saved successfully</span></div>		<div class="articleFeedback-pending articleFeedback-visibleWith-form"><span>Your ratings have not been submitted yet</span></div>		<div style="clear:both;"></div>		<div class="articleFeedback-notices articleFeedback-visibleWith-form">			<div class="articleFeedback-expiry">				<div class="articleFeedback-expiry-title">Your ratings have expired</div>				<div class="articleFeedback-expiry-message">Please reevaluate this page and submit new ratings.</div>			</div>		</div>	</div>	<div class="articleFeedback-error"><div class="articleFeedback-error-message">An error has occurred. Please try again later.</div></div>	<div class="articleFeedback-pitches"><div rel="join" class="articleFeedback-pitch">	<div class="articleFeedback-buffer">		<div class="articleFeedback-title">Thanks! Your ratings have been saved.</div>		<div class="articleFeedback-pop">			<div class="articleFeedback-message">Do you want to create an account?</div>			<div class="articleFeedback-body">An account will help you track your edits, get involved in discussions, and be a part of the community.</div>			<button aria-disabled="false" role="button" class="articleFeedback-accept ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only ui-button-green"><span class="ui-button-text">Create an account</span></button><span class="articleFeedback-pitch-or">or</span><button aria-disabled="false" role="button" class="articleFeedback-altAccept ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only ui-button-green"><span class="ui-button-text">Log in</span></button>			<button class="articleFeedback-reject">Maybe later</button>		</div>	</div></div><div rel="edit" class="articleFeedback-pitch">	<div class="articleFeedback-buffer">		<div class="articleFeedback-title">Thanks! Your ratings have been saved.</div>		<div class="articleFeedback-pop">			<div class="articleFeedback-message">Did you know that you can edit this page?</div>			<div class="articleFeedback-body"></div>			<button aria-disabled="false" role="button" class="articleFeedback-accept ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only ui-button-green"><span class="ui-button-text">Edit this page</span></button>			<button class="articleFeedback-reject">Maybe later</button>		</div>	</div></div></div>	<div style="clear:both;"></div></div><div class="articleFeedback-lock"></div>		</div><div id="catlinks" class="catlinks"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="http://en.wikipedia.org/wiki/Special:Categories" title="Special:Categories">Categories</a>: <ul><li><a href="http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms" title="Category:Lossless compression algorithms">Lossless compression algorithms</a></li><li><a href="http://en.wikipedia.org/wiki/Category:Transforms" title="Category:Transforms">Transforms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="http://en.wikipedia.org/wiki/Category:Wikipedia_articles_needing_copy_edit_from_September_2012" title="Category:Wikipedia articles needing copy edit from September 2012">Wikipedia articles needing copy edit from September 2012</a></li><li><a href="http://en.wikipedia.org/wiki/Category:All_articles_needing_copy_edit" title="Category:All articles needing copy edit">All articles needing copy edit</a></li><li><a href="http://en.wikipedia.org/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="http://en.wikipedia.org/wiki/Category:Articles_with_unsourced_statements_from_September_2012" title="Category:Articles with unsourced statements from September 2012">Articles with unsourced statements from September 2012</a></li><li><a href="http://en.wikipedia.org/wiki/Category:Articles_with_example_pseudocode" title="Category:Articles with example pseudocode">Articles with example pseudocode</a></li><li><a href="http://en.wikipedia.org/wiki/Category:Articles_with_example_Python_code" title="Category:Articles with example Python code">Articles with example Python code</a></li></ul></div></div>				<!-- /catlinks -->
												<div class="visualClear"></div>
				<!-- debughtml -->
								<!-- /debughtml -->
			</div>
			<!-- /bodyContent -->
		</div>
		<!-- /content -->
		<div id="mw-navigation">
			<h2>Navigation menu</h2>
			<!-- header -->
			<div id="mw-head" class="noprint">
				
<!-- 0 -->
<div id="p-personal" role="navigation" class="">
	<h3>Personal tools</h3>
	<ul>
<li id="pt-createaccount"><a href="http://en.wikipedia.org/w/index.php?title=Special:UserLogin&amp;returnto=Burrows%E2%80%93Wheeler+transform&amp;type=signup">Create account</a></li><li id="pt-login"><a href="http://en.wikipedia.org/w/index.php?title=Special:UserLogin&amp;returnto=Burrows%E2%80%93Wheeler+transform" title="You are encouraged to log in; however, it is not mandatory. [alt-shift-o]" accesskey="o">Log in</a></li>	</ul>
</div>

<!-- /0 -->
				<div id="left-navigation">
					
<!-- 0 -->
<div id="p-namespaces" role="navigation" class="vectorTabs">
	<h3>Namespaces</h3>
	<ul>
					<li id="ca-nstab-main" class="selected"><span><a href="http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" title="View the content page [alt-shift-c]" accesskey="c">Article</a></span></li>
					<li id="ca-talk"><span><a href="http://en.wikipedia.org/wiki/Talk:Burrows%E2%80%93Wheeler_transform" title="Discussion about the content page [alt-shift-t]" accesskey="t">Talk</a></span></li>
			</ul>
</div>

<!-- /0 -->

<!-- 1 -->
<div id="p-variants" role="navigation" class="vectorMenu emptyPortlet">
	<h3 id="mw-vector-current-variant">
		</h3>
	<h3><span>Variants</span><a href="#"></a></h3>
	<div class="menu">
		<ul>
					</ul>
	</div>
</div>

<!-- /1 -->
				</div>
				<div id="right-navigation">
					
<!-- 0 -->
<div id="p-views" role="navigation" class="vectorTabs">
	<h3>Views</h3>
	<ul>
					<li id="ca-view" class="selected"><span><a href="http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform">Read</a></span></li>
					<li id="ca-edit"><span><a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=edit" title="You can edit this page. 
Please use the preview button before saving. [alt-shift-e]" accesskey="e">Edit</a></span></li>
					<li id="ca-history" class="collapsible"><span><a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=history" title="Past versions of this page [alt-shift-h]" accesskey="h">View history</a></span></li>
			</ul>
</div>

<!-- /0 -->

<!-- 1 -->
<div id="p-cactions" role="navigation" class="vectorMenu emptyPortlet">
	<h3><span>Actions</span><a href="#"></a></h3>
	<div class="menu">
		<ul>
					</ul>
	</div>
</div>

<!-- /1 -->

<!-- 2 -->
<div id="p-search" role="search">
	<h3><label for="searchInput">Search</label></h3>
	<form action="/w/index.php" id="searchform">
				<div id="simpleSearch">
						<input tabindex="1" placeholder="Search" autocomplete="off" name="search" title="Search Wikipedia [alt-shift-f]" accesskey="f" id="searchInput">						<button type="submit" name="button" title="Search Wikipedia for this text" id="searchButton"><img src="WikipediaBurrows%E2%80%93Wheeler_transform_files/search-ltr.png" alt="Search" height="13" width="12"></button>								<input name="title" value="Special:Search" type="hidden">
		</div>
	</form>
</div>

<!-- /2 -->
				</div>
			</div>
			<!-- /header -->
			<!-- panel -->
			<div id="mw-panel" class="noprint collapsible-nav">
				<!-- logo -->
					<div id="p-logo" role="banner"><a style="background-image: url(//upload.wikimedia.org/wikipedia/en/b/bc/Wiki.png);" href="http://en.wikipedia.org/wiki/Main_Page" title="Visit the main page"></a></div>
				<!-- /logo -->
				
<!-- navigation -->
<div class="portal first persistent" role="navigation" id="p-navigation">
	<h3>Navigation</h3>
	<div class="body">
		<ul>
			<li id="n-mainpage-description"><a href="http://en.wikipedia.org/wiki/Main_Page" title="Visit the main page [alt-shift-z]" accesskey="z">Main page</a></li>
			<li id="n-contents"><a href="http://en.wikipedia.org/wiki/Portal:Contents" title="Guides to browsing Wikipedia">Contents</a></li>
			<li id="n-featuredcontent"><a href="http://en.wikipedia.org/wiki/Portal:Featured_content" title="Featured content – the best of Wikipedia">Featured content</a></li>
			<li id="n-currentevents"><a href="http://en.wikipedia.org/wiki/Portal:Current_events" title="Find background information on current events">Current events</a></li>
			<li id="n-randompage"><a href="http://en.wikipedia.org/wiki/Special:Random" title="Load a random article [alt-shift-x]" accesskey="x">Random article</a></li>
			<li id="n-sitesupport"><a href="http://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&amp;utm_medium=sidebar&amp;utm_campaign=C12_en.wikipedia.org&amp;uselang=en" title="Support us">Donate to Wikipedia</a></li>
		</ul>
	</div>
</div>

<!-- /navigation -->

<!-- SEARCH -->

<!-- /SEARCH -->

<!-- interaction -->
<div class="portal expanded" role="navigation" id="p-interaction">
	<h3 tabindex="2"><a href="#">Interaction</a></h3>
	<div style="display: block;" class="body">
		<ul>
			<li id="n-help"><a href="http://en.wikipedia.org/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia">Help</a></li>
			<li id="n-aboutsite"><a href="http://en.wikipedia.org/wiki/Wikipedia:About" title="Find out about Wikipedia">About Wikipedia</a></li>
			<li id="n-portal"><a href="http://en.wikipedia.org/wiki/Wikipedia:Community_portal" title="About the project, what you can do, where to find things">Community portal</a></li>
			<li id="n-recentchanges"><a href="http://en.wikipedia.org/wiki/Special:RecentChanges" title="A list of recent changes in the wiki [alt-shift-r]" accesskey="r">Recent changes</a></li>
			<li id="n-contact"><a href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia">Contact Wikipedia</a></li>
		</ul>
	</div>
</div>

<!-- /interaction -->

<!-- TOOLBOX -->
<div class="portal collapsed" role="navigation" id="p-tb">
	<h3 tabindex="3"><a href="#">Toolbox</a></h3>
	<div class="body">
		<ul>
			<li id="t-whatlinkshere"><a href="http://en.wikipedia.org/wiki/Special:WhatLinksHere/Burrows%E2%80%93Wheeler_transform" title="List of all English Wikipedia pages containing links to this page [alt-shift-j]" accesskey="j">What links here</a></li>
			<li id="t-recentchangeslinked"><a href="http://en.wikipedia.org/wiki/Special:RecentChangesLinked/Burrows%E2%80%93Wheeler_transform" title="Recent changes in pages linked from this page [alt-shift-k]" accesskey="k">Related changes</a></li>
			<li id="t-upload"><a href="http://en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [alt-shift-u]" accesskey="u">Upload file</a></li>
			<li id="t-specialpages"><a href="http://en.wikipedia.org/wiki/Special:SpecialPages" title="A list of all special pages [alt-shift-q]" accesskey="q">Special pages</a></li>
			<li id="t-permalink"><a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;oldid=526993356" title="Permanent link to this revision of the page">Permanent link</a></li>
			<li id="t-info"><a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;action=info">Page information</a></li>
<li id="t-cite"><a href="http://en.wikipedia.org/w/index.php?title=Special:Cite&amp;page=Burrows%E2%80%93Wheeler_transform&amp;id=526993356" title="Information on how to cite this page">Cite this page</a></li>		<li id="t-articlefeedback"><a href="#mw-articlefeedback">Rate this page</a></li></ul>
	</div>
</div>

<!-- /TOOLBOX -->

<!-- coll-print_export -->
<div class="portal collapsed" role="navigation" id="p-coll-print_export">
	<h3 tabindex="4"><a href="#">Print/export</a></h3>
	<div class="body">
		<ul id="collectionPortletList"><li id="coll-create_a_book"><a href="http://en.wikipedia.org/w/index.php?title=Special:Book&amp;bookcmd=book_creator&amp;referer=Burrows%E2%80%93Wheeler+transform" title="Create a book or page collection" rel="nofollow">Create a book</a></li><li id="coll-download-as-rl"><a href="http://en.wikipedia.org/w/index.php?title=Special:Book&amp;bookcmd=render_article&amp;arttitle=Burrows%E2%80%93Wheeler+transform&amp;oldid=526993356&amp;writer=rl" title="Download a PDF version of this wiki page" rel="nofollow">Download as PDF</a></li><li id="t-print"><a href="http://en.wikipedia.org/w/index.php?title=Burrows%E2%80%93Wheeler_transform&amp;printable=yes" title="Printable version of this page [alt-shift-p]" accesskey="p">Printable version</a></li></ul>	</div>
</div>

<!-- /coll-print_export -->

<!-- LANGUAGES -->
<div class="portal expanded" role="navigation" id="p-lang">
	<h3 tabindex="5"><a href="#">Languages</a></h3>
	<div style="display: block;" class="body">
		<ul>
			<li class="interwiki-cs"><a href="http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace" title="Burrowsova-Wheelerova transformace" hreflang="cs" lang="cs">Česky</a></li>
			<li class="interwiki-de"><a href="http://de.wikipedia.org/wiki/Burrows-Wheeler-Transformation" title="Burrows-Wheeler-Transformation" hreflang="de" lang="de">Deutsch</a></li>
			<li class="interwiki-es"><a href="http://es.wikipedia.org/wiki/Compresi%C3%B3n_de_Burrows-Wheeler" title="Compresión de Burrows-Wheeler" hreflang="es" lang="es">Español</a></li>
			<li class="interwiki-fa"><a href="http://fa.wikipedia.org/wiki/%D8%AA%D8%A8%D8%AF%DB%8C%D9%84_%D8%A8%D8%A7%D8%B1%D9%88%D8%B2-%D9%88%DB%8C%D9%84%D8%B1" title="تبدیل باروز-ویلر" hreflang="fa" lang="fa">فارسی</a></li>
			<li class="interwiki-fr"><a href="http://fr.wikipedia.org/wiki/Transform%C3%A9e_de_Burrows-Wheeler" title="Transformée de Burrows-Wheeler" hreflang="fr" lang="fr">Français</a></li>
			<li class="interwiki-ko"><a href="http://ko.wikipedia.org/wiki/%EB%B2%84%EB%A1%9C%EC%9A%B0%EC%A6%88-%ED%9C%A0%EB%9F%AC_%EB%B3%80%ED%99%98" title="버로우즈-휠러 변환" hreflang="ko" lang="ko">한국어</a></li>
			<li class="interwiki-it"><a href="http://it.wikipedia.org/wiki/Trasformata_di_Burrows-Wheeler" title="Trasformata di Burrows-Wheeler" hreflang="it" lang="it">Italiano</a></li>
			<li class="interwiki-hu"><a href="http://hu.wikipedia.org/wiki/Burrows-Wheeler_transzform%C3%A1ci%C3%B3" title="Burrows-Wheeler transzformáció" hreflang="hu" lang="hu">Magyar</a></li>
			<li class="interwiki-nl"><a href="http://nl.wikipedia.org/wiki/Burrows-Wheelertransformatie" title="Burrows-Wheelertransformatie" hreflang="nl" lang="nl">Nederlands</a></li>
			<li class="interwiki-ja"><a href="http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88" title="ブロックソート" hreflang="ja" lang="ja">日本語</a></li>
			<li class="interwiki-pl"><a href="http://pl.wikipedia.org/wiki/Transformata_Burrowsa-Wheelera" title="Transformata Burrowsa-Wheelera" hreflang="pl" lang="pl">Polski</a></li>
			<li class="interwiki-pt"><a href="http://pt.wikipedia.org/wiki/M%C3%A9todo_de_Burrows-Wheeler" title="Método de Burrows-Wheeler" hreflang="pt" lang="pt">Português</a></li>
			<li class="interwiki-ru"><a href="http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0" title="Преобразование Барроуза — Уилера" hreflang="ru" lang="ru">Русский</a></li>
			<li class="interwiki-zh"><a href="http://zh.wikipedia.org/wiki/Burrows-Wheeler%E5%8F%98%E6%8D%A2" title="Burrows-Wheeler变换" hreflang="zh" lang="zh">中文</a></li>
		</ul>
	</div>
</div>

<!-- /LANGUAGES -->
			</div>
			<!-- /panel -->
		</div>
		<!-- footer -->
		<div id="footer" role="contentinfo">
							<ul id="footer-info">
											<li id="footer-info-lastmod"> This page was last modified on 8 December 2012 at 08:37.<br></li>
											<li id="footer-info-copyright">Text is available under the <a rel="license" href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License">Creative Commons Attribution-ShareAlike License</a><a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/" style="display:none;"></a>;
additional terms may apply.
See <a href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</a> for details.<br>
Wikipedia® is a registered trademark of the <a href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.<br></li><li class="noprint"><a class="internal" href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</a></li>
									</ul>
							<ul id="footer-places">
											<li id="footer-places-privacy"><a href="http://wikimediafoundation.org/wiki/Privacy_policy" title="wikimedia:Privacy policy">Privacy policy</a></li>
											<li id="footer-places-about"><a href="http://en.wikipedia.org/wiki/Wikipedia:About" title="Wikipedia:About">About Wikipedia</a></li>
											<li id="footer-places-disclaimer"><a href="http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer" title="Wikipedia:General disclaimer">Disclaimers</a></li>
											<li id="footer-places-mobileview"><a href="http://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" class="noprint stopMobileRedirectToggle">Mobile view</a></li>
									</ul>
										<ul id="footer-icons" class="noprint">
					<li id="footer-copyrightico">
						<a href="http://wikimediafoundation.org/"><img src="WikipediaBurrows%E2%80%93Wheeler_transform_files/wikimedia-button.png" alt="Wikimedia Foundation" height="31" width="88"></a>
					</li>
					<li id="footer-poweredbyico">
						<a href="http://www.mediawiki.org/"><img src="WikipediaBurrows%E2%80%93Wheeler_transform_files/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" height="31" width="88"></a>
					</li>
				</ul>
						<div style="clear:both"></div>
		</div>
		<!-- /footer -->
		<script>if(window.mw){
mw.loader.state({"site":"loading","user":"ready","user.groups":"ready"});
}</script>
<script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_005.php"></script>
<script>if(window.mw){
mw.loader.load(["mobile.desktop","mediawiki.user","mediawiki.page.ready","mediawiki.searchSuggest","mediawiki.hidpi","ext.gadget.teahouse","ext.gadget.ReferenceTooltips","ext.gadget.DRN-wizard","ext.gadget.charinsert","mw.MwEmbedSupport.style","ext.vector.collapsibleNav","ext.vector.collapsibleTabs","ext.vector.editWarning","ext.UserBuckets","ext.articleFeedback.startup","ext.articleFeedbackv5.startup","ext.markAsHelpful","ext.Experiments.experiments","mw.PopUpMediaTransform"], null, true);
}</script>
<script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/index.php"></script>
<script src="WikipediaBurrows%E2%80%93Wheeler_transform_files/load_009.php"></script>
<!-- Served by mw31 in 0.167 secs. -->
	

<div class="suggestions" style="display: none; font-size: 13px;"><div class="suggestions-results"></div><div class="suggestions-special"></div></div></body></html>